无重复字符的最长子串

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

例如：

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

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

• 输入：s = "pwwkew"
  输出：3
  解释：因为无重复字符的最长子串是 "wke"，长度为3（注意 "pwke" 是一个子序列而非连续子串）。

解题思路
我们使用 滑动窗口 配合 哈希表（或哈希集合） 来高效解决。核心思想是：

1. 维护一个 窗口，窗口内的字符都是不重复的。
2. 用哈希集合快速判断当前字符是否已经在窗口中出现过。
3. 如果遇到重复字符，则 移动窗口左边界，直到重复字符被移出窗口。
4. 在遍历过程中，持续记录窗口的最大长度。

步骤详解

步骤1：初始化

• 定义两个指针 left 和 right，分别表示窗口的左右边界（初始都为0）。
• 定义一个哈希集合 charSet，用于存储当前窗口内的字符。
• 定义变量 maxLen 记录最大长度（初始为0）。

步骤2：遍历字符串
我们让 right 指针从0开始逐步向右移动，遍历每个字符。

示例：以 s = "abcabcbb" 为例。

1. right=0：字符 'a'

   • charSet 中无 'a'，加入集合 → {'a'}。
   • 当前窗口长度 = right-left+1 = 1，更新 maxLen = max(0,1)=1。
   • right 右移 → right=1。

2. right=1：字符 'b'

   • charSet 中无 'b'，加入集合 → {'a','b'}。
   • 当前长度 = 2，maxLen=2。
   • right=2。

3. right=2：字符 'c'

   • 无重复，加入集合 → {'a','b','c'}。
   • 长度 = 3，maxLen=3。
   • right=3。

步骤3：遇到重复字符时的处理
4. right=3：字符 'a'

• 此时 charSet = {'a','b','c'}，发现 'a' 已存在！
• 需要移动 left 指针，直到重复字符 'a' 被移出窗口：
  • 将 s[left]（即 'a'）从 charSet 中移除 → {'b','c'}。
  • left 右移一位（left=1）。
• 现在窗口内无 'a' 了，将当前字符 'a' 加入集合 → {'b','c','a'}。
• 当前长度 = right-left+1 = 3-1+1=3，maxLen 保持3。
• right=4。

关键逻辑：
每当遇到重复字符，我们就不断从哈希集合中移除 s[left] 并左移 left，直到重复字符被移出集合。这样保证窗口内始终无重复。

步骤4：继续遍历
5. right=4：字符 'b'

• 集合为 {'b','c','a'}，'b' 存在。
• 移除 s[left]（left=1，字符 'b'）→ {'c','a'}，left=2。
• 仍存在 'b' 吗？集合中已无 'b'，所以停止左移。
• 加入 'b' → {'c','a','b'}。
• 长度 = 4-2+1=3，maxLen=3。
• right=5。

6. right=5：字符 'c'

   • 集合 {'c','a','b'}，'c' 存在。
   • 移除 s[left]（left=2，字符 'c'）→ {'a','b'}，left=3。
   • 集合中已无 'c'，加入 'c' → {'a','b','c'}。
   • 长度 = 3，maxLen=3。
   • right=6。

7. right=6：字符 'b'

   • 集合 {'a','b','c'}，'b' 存在。
   • 移除 s[left]（left=3，字符 'a'）→ {'b','c'}，left=4。
   • 仍有 'b'？存在！继续：移除 s[left]（left=4，字符 'b'）→ {'c'}，left=5。
   • 集合中已无 'b'，加入 'b' → {'c','b'}。
   • 长度 = 2，maxLen=3。
   • right=7。

8. right=7：字符 'b'

   • 集合 {'c','b'}，'b' 存在。
   • 移除 s[left]（left=5，字符 'c'）→ {'b'}，left=6。
   • 仍有 'b'？存在！继续：移除 s[left]（left=6，字符 'b'）→ {}，left=7。
   • 加入 'b' → {'b'}。
   • 长度 = 1，maxLen=3。
   • 遍历结束。

步骤5：返回结果
最终 maxLen = 3，即为最长无重复字符子串的长度。

时间复杂度分析

• 每个字符最多被 left 和 right 指针访问一次（加入集合一次、移除集合一次）。
• 时间复杂度：O(n)，其中 n 是字符串长度。
• 空间复杂度：O(min(m, n))，m 是字符集大小（例如 ASCII 为128），哈希集合存储窗口内字符。

代码实现（Python示例）

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

总结
这道题通过 滑动窗口 和 哈希集合 的结合，高效地找到了无重复字符的最长子串。关键在于用哈希集合快速判断重复，并通过移动左边界维护窗口的有效性。