无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

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

示例 3:

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

提示：

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

运行时间: 76 ms

内存: 17 MB

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        memo = defaultdict(int)
        ret = 0
        l = r = 0
        while r < len(s):
            c = s[r]
            memo[c] += 1
            r += 1
            while memo[c] > 1:
                d = s[l]
                l += 1
                if d in memo:
                    memo[d] -= 1

            ret = max(ret, r - l)
        return ret

这个题解使用了滑动窗口的思路。用两个指针 l 和 r 表示滑动窗口的左右边界，用一个哈希表 memo 记录窗口内每个字符出现的次数。每次移动右指针 r，将新字符加入窗口，并更新哈希表。如果发现哈希表中新加入字符的次数大于1，说明有重复字符，则移动左指针 l 缩小窗口，并更新哈希表，直到窗口内没有重复字符为止。在移动过程中，用一个变量 ret 来记录最长无重复字符子串的长度。

时间复杂度: O(n)

空间复杂度: O(min(m, n))

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        memo = defaultdict(int)  # 记录每个字符出现的次数
        ret = 0  # 记录最长无重复字符子串的长度
        l = r = 0  # 滑动窗口的左右指针
        while r < len(s):
            c = s[r]  # 右指针指向的新字符
            memo[c] += 1  # 将新字符加入哈希表
            r += 1  # 右指针右移
            while memo[c] > 1:  # 如果新加入的字符导致重复
                d = s[l]  # 左指针指向的字符
                l += 1  # 左指针右移
                if d in memo:
                    memo[d] -= 1  # 更新哈希表，缩小窗口
            
            ret = max(ret, r - l)  # 更新最长无重复字符子串的长度
        return ret