3. 无重复字符的最长子串

Difficulty
Medium
Tags
滑动窗口
双指针
URL
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
Star
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入:s = "abcabcbb"
输出:3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入:s = "bbbbb"
输出:1
解释:因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入:s = "pwwkew"
输出:3
解释:因为无重复字符的最长子串是"wke"，所以其长度为 3。
     请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入:s = ""
输出:0
提示：
  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

滑动窗口

思路
滑动窗口，每次往前走一步，都判断一下当前窗口有无重复字符，如果有的话，就收缩left,直到没有重复字符。因为是没往前走一步都判断，所以只有当前字符可能会重复，之前的一定不会重复。且s[left:right} 一定都在窗口中。
题解
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right = 0, 0
        res = 0
        window = collections.defaultdict(int)
        while right < len(s):
            cur = s[right]
            right += 1

            window[cur] += 1

            while window[cur] > 1:
                dele = s[left]
                left += 1
                window[dele] -= 1

            res = max(res, right - left)

        return res