leetcode-无重复字符的最长子串

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

def lengthOfLongestSubstring(self, s: str) -> int:
    # 写一个滑动窗口
    # 开始的时候左面指针是0
    # 每次移动右面元素，判断窗口内元素是否合法，如果不合法就移动左指针直到合法
    # 如何判断窗口内元素是否合法？使用字典或者set
    left = 0
    max_size = 0
    char_set = set()
    for right in range(len(s)):
        if s[right] in char_set:
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
        
        char_set.add(s[right])
        max_size = max(max_size, len(char_set))

    return max_size

核心问题：

如何快速判断窗口内有没有重复？用 HashSet / hashmap 记录窗口内容

Step 1：右指针扩张 不断加入新字符。
Step 2：如果重复 左指针一直移动直到合法
Step 3：更新最大长度

核心思想就是：先扩张，再修复
对于固定窗口就简单了，就是right++ → left++