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

🎯 问题描述（来源于LeetCode）

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

说明：

子串：字符串中一段连续非空的字符序列。
核心逻辑：使用滑动窗口维护一个“无重复字符”的区间。当遇到重复字符时，收缩左边界，直到窗口内再次满足无重复条件。
示例：
示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

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

💻 解题思路

思路1：不定长滑动窗口

思路1：代码实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0             # 记录最长子串的长度
        cnt = Counter()     # 哈希表，记录窗口内每个字符出现的次数
        left = 0            # 窗口左边界
        
        # 右边界 right 随循环遍历字符串
        for right, c in enumerate(s):
            # 1. 扩展窗口：将当前字符加入哈希表
            cnt[c] += 1
            
            # 2. 收缩窗口：如果当前字符出现次数超过 1（即出现重复）
            # 则不断移动左边界，直到当前字符次数恢复为 1
            while cnt[c] > 1:
                cnt[s[left]] -= 1
                left += 1
            
            # 3. 更新答案：此时窗口 [left, right] 内无重复字符
            ans = max(ans, right - left + 1)
            
        return ans

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是字符串 s 的长度。
- 虽然代码中有一个 while 循环嵌套在 for 循环中，但每个字符最多被访问两次（一次被右边界 right 加入，一次被左边界 left 移出）。因此，整体操作次数是线性的。
空间复杂度： $O(\min(M, N))$ $O (min (M, N))$
- 其中 $M$ 是字符集的大小（例如 ASCII 字符集大小为 128）。
- 哈希表 cnt 最多存储 $M$ 个字符的计数。如果字符集很大，则受限于字符串长度 $N$ 。

思考

不定长窗口：
- 与之前的定长窗口不同，这里的窗口大小是动态变化的。
- 右边界 right 始终向右移动。
- 左边界 left 只有在遇到重复字符（cnt[c] > 1）时才会向右移动。
收缩逻辑：
- while cnt[c] > 1: 是核心。它保证了在任何时刻，窗口内的所有字符出现次数都不超过 1。
- 当发现重复字符 c 时，我们不断移除左边的字符，直到那个重复的 c 被移除一个为止。
答案更新时机：
- ans = max(ans, right - left + 1) 放在 while 循环之后。
- 这保证了我们只在窗口满足“无重复字符”这一合法条件时，才去更新最大长度。
Counter 的使用：
- 使用 collections.Counter 可以方便地处理字符计数，比普通的字典操作更简洁（例如不需要判断键是否存在）。