注意：这里是“子串”，不是“子序列”#

• 子串：必须连续
• 子序列：可以不连续

这题要的是连续的一段， 所以非常适合用滑动窗口来做。

1. counter 记录窗口内每个字符出现了几次#

1
counter = Counter()

这个哈希表的作用是：

• 键：字符
• 值：该字符在当前窗口中出现的次数

比如当前窗口是：

1
"abca"

那么：

1
counter = {
2
    'a': 2,
3
    'b': 1,
4
    'c': 1
5
}

一眼就能看出：

• a 重复了
• 当前窗口不合法

2. right 负责把窗口往右扩张#

1
for right in range(n):
2
    counter[s[right]] += 1

每次遍历到一个新字符， 就把它纳入窗口。

这一步相当于说：

“先把这个字符收进来，再看窗口还合不合法。”

3. 一旦出现重复，就不断收缩左边界#

1
while left <= right and counter[s[right]] > 1:
2
    counter[s[left]] -= 1
3
    left += 1

这是整题最关键的一步。

为什么判断条件写成：

1
counter[s[right]] > 1

因为当前新加入窗口、导致问题出现的，就是 s[right]。

如果它的出现次数大于 1， 说明当前窗口里有重复字符，必须收缩。

收缩时要注意顺序：

1. 先把 s[left] 的计数减一
2. 再把 left 右移

这个顺序很重要。

如果顺序反了，逻辑就会拧巴， 甚至可能把计数维护错位。

4. 窗口合法后更新答案#

1
ans = max(ans, right - left + 1)

当 while 结束时， 说明当前窗口已经重新变成“不含重复字符”的合法窗口。

这时窗口长度就是：

1
right - left + 1

拿它和历史最大值比较，更新答案即可。

初始状态#

• left = 0
• ans = 0
• 窗口为空

right = 0，加入 'a'#

窗口变成：

1
"a"

没有重复，长度为 1。

1
ans = 1

right = 1，加入 'b'#

窗口变成：

1
"ab"

没有重复，长度为 2。

1
ans = 2

right = 2，加入 'c'#

窗口变成：

1
"abc"

没有重复，长度为 3。

1
ans = 3

right = 3，加入 'a'#

窗口变成：

1
"abca"

此时 'a' 重复了。

开始收缩左边界：

• 移除左边第一个 'a'
• left 从 0 移到 1

窗口重新变成：

1
"bca"

又合法了，长度还是 3。

后面继续同理#

窗口会不断经历：

• 右边扩张
• 出现重复
• 左边收缩
• 恢复合法

最终最长长度就是：

1
3

时间复杂度#

虽然看起来有一层 for 和一层 while， 但 left 和 right 都只会从左到右各走一遍。

所以总时间复杂度是：

1
O(n)

空间复杂度#

哈希表最多记录字符集中的若干字符， 一般记作：

1
O(k)

其中 k 是字符集大小。

如果按字符串长度上界来写，也可以记成：

1
O(n)

1. 窗口不合法时，不是推倒重来，而是慢慢缩#

滑动窗口的魅力就在这：

• 能扩就扩
• 不合法就缩
• 没必要把整个窗口作废重建

2. 重复的判断依赖计数，不只是看存不存在#

这也是为什么这版本质上是“哈希计数”，而不是纯 set。

3. 更新答案必须在窗口恢复合法之后#

如果窗口里还有重复字符就去更新长度， 那答案就会掺水。