【LC 3】无重复字符的最长子串：判据不是「字符出现过」，而是「它还在窗口里」
适用读者：想学滑动窗口、但被这道题的各种边界情况绕晕过的人
技术栈：Python 为主，附 Java 版
难度：中等 —— 代码 10 行，但有一个条件是漏了就必错的
收获：滑动窗口的两条不变量、left 为什么只能右移，以及 159 / 340 / 424 / 76 / 209 / 438 一整串变体的分岔点
题目
给定一个字符串
s，请你找出其中
不含有重复字符的最长子串的长度。
输入：s = "abcabcbb"
输出：3
解释：最长无重复子串是 "abc"，长度为 3。
输入：s = "bbbbb"
输出：1
解释：最长无重复子串是 "b"，长度为 1。
输入：s = "pwwkew"
输出：3
解释：最长无重复子串是 "wke"，长度为 3。注意答案必须是子串（连续的一段），"pwke" 是子序列，不是子串。
出处备注：这道题在字节跳动的面经里长期排第一（腾讯那边也在前三）。原因很直接 —— 它是滑动窗口的入门模板，写完只要 10 行，但能同时问出三件事：你懂不懂"子串必须连续"、你懂不懂"维护什么信息"、你懂不懂"左指针为什么不能回头"。
子串 vs 子序列，先分清（面试官真的会抓）：
这题要的是
子串。所以答案是 3（
"wke"），不是 4（
"pwke"）。
一、先说清楚这题在考什么
1.1 暴力为什么不划算
最直白的想法：枚举所有子串，逐个检查有没有重复。
def lengthOfLongestSubstring(s):
n, best = len(s), 0
for i in range(n): # 枚举左端点
for j in range(i, n): # 枚举右端点
if len(set(s[i:j + 1])) == j - i + 1:
best = max(best, j - i + 1)
return best
（枚举是 n²，每次还要 O(n) 检查重复）。n = 5×10⁴ 时直接超时。
问题在于
枚举本身是浪费的：如果
s[i..j] 有重复，那么
s[i..j+1]、
s[i..j+2]… 全都有重复。这些右端点根本不用试。
1.2 换个角度：维护一个"永远合法"的窗口
不要枚举，而是
维护一个窗口 [left, right]，让它始终满足条件，然后一路往右推：
left right
↓ ↓
p w w k e w ...
└──────────┘
这个窗口里永远没有重复字符
规则只有两条：
right 每次都往右走一格（把新字符吃进窗口）；- 如果吃进来的字符在窗口内已经存在，就让
left 跳到"那个旧位置 + 1"，把它挤出窗口。
两个指针
都只往右走，所以总共走不超过
2n 步 ——
O(n)。
这就是
滑动窗口：一条长度可变的、始终满足某个性质的连续区间。
1.3 需要维护什么信息
要在 O(1) 里回答"新字符在窗口内出现过吗"，就得有一张表。
表里存什么？
两者都是 O(n)，但
lastSeen 版本
没有内层循环，常数更小 —— 因为左指针是"跳"过去的，不是"挪"过去的。
关键点：
lastSeen 里存的是
下标，不是"是否存在"这个布尔值。这个区别就是下一节的全部内容。
二、两条不变量（本题的灵魂）
理解这题的关键，是先立下两条
必须始终成立的性质：
不变量 1：窗口 [left, right] 内永远没有重复字符
这是"窗口合法"的定义，也是所有长度计算的前提。
ans = right - left + 1 只有在窗口合法时才是有意义的答案。
不变量 2：left 只往右走，绝不后退
这条容易被忽略，但它是
第一条不变量能成立的原因。
为什么
left 后退会破掉第一条？因为窗口左边界一旦往回退，就把"之前为了去重而挤出去的字符"
又放了回来 —— 而那些字符在窗口右半部分可能还留着。于是窗口里立刻出现重复。
把 left 从 2 退回到 1：
a b b a 窗口 [1,3] = "bba"
└─────┘ ← 两个 b！不变量 1 当场破掉
↑
倒退到这里
三、完整代码
3.1 推荐写法：把"是否还在窗口内"显式写出来
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last = {} # 字符 -> 它最后出现的下标
left = 0
ans = 0
for right, ch in enumerate(s):
# 关键条件：出现过，并且那个位置还在窗口里
if ch in last and last[ch] >= left:
left = last[ch] + 1 # 把它挤出窗口
last[ch] = right # 记录/更新它的最后位置
ans = max(ans, right - left + 1)
return ans
：判据
last[ch] >= left 把"为什么是这条件"直接摆在代码里。
3.2 等价写法：把保护藏进 max
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last = {}
left = 0
ans = 0
for right, ch in enumerate(s):
if ch in last:
left = max(left, last[ch] + 1) # ← max 就是那个"不许倒退"
last[ch] = right
ans = max(ans, right - left + 1)
return ans
两次写法的区别只在一行：
# 写法 A：先判断"是否还在窗口内"，再决定跳不跳
if ch in last and last[ch] >= left:
left = last[ch] + 1
# 写法 B：无条件算一个候选值，再靠 max 拦住倒退
if ch in last:
left = max(left, last[ch] + 1)
。写法 A 更"讲道理"，写法 B 更短。
理解要点在于：知道 max 在这里到底在拦什么。
四、动画：看着窗口左右两端一起往右爬
下面这个动画把上面 10 帧推演过程逐帧画出来。图里：
- 一排字符格子 = 原串；在窗口内的淡绿底，已经被挤出窗口的灰掉；
- 橙色格子 + 上方
right 指针 = 这一帧正在处理的字符；
- 绿色横条 = 当前窗口
[left, right]，两端标出 L= 和 R=；
- 金色下划线 = 目前为止最优的那个窗口（答案对应的区间）；
- 下方
lastSeen 表 = 每个字符最后出现在哪。这一帧涉及的字符，卡片会显示"它的旧位置"（金色数字），方便和讲解对上。
看的时候重点盯三处：
- 第 4 帧（下标 3 的
a）：a 上次在下标 0，而 0 还在窗口里 → left 从 0 一步跳到 1，窗口从 [0,2] 变成 [1,3]。注意左边界是跳过去的，不是一格一格挪；
- 第 7 帧（下标 6 的
b）：b 上次在下标 4，left 从 3 跳到 5 —— 跨了两格，把 4 和 5 之间的东西一次全挤出窗口；
ans 从第 4 帧开始就一直是 3，再也没变过。后面 4 帧窗口一直在缩，但答案不再增长。这正是"窗口长度不等于答案"的直观体现。
五、完整推演表（10 帧逐帧）
下表是动画每一帧的真实数据（默认例
s = "abcabcbb"）：
三个值得对照看的行：
第 3 帧 —— 前三步都是
expand，因为
a /
b /
c 都是第一次见，窗口一路长到 3，
ans 也涨到 3。
第 4 帧 ——
right 走到下标 3，字符又是
a。查表：
last['a'] = 0，而
left = 0，
0 >= 0 成立 → 它在窗口里。于是
left = 0 + 1 = 1。
第 7 帧 ——
right = 6，字符
b。
last['b'] = 4，
left 此刻是 3，
4 >= 3 成立 →
left = 5。
一次跨过两格，窗口从
[3,5] 缩到
[5,6]。
注意最后两帧：
ans 停在 3 不动了。
窗口在缩，答案不缩 —— 因为
ans 记的是"历史最大值"，不是"当前窗口长度"。
六、本题唯一真正的难点：判据里必须有"还在窗口里"这半句
现在来到全文最关键的一节。
很多人第一次写这题，会写成这样：
if ch in last:
left = last[ch] + 1 # ❌ 漏掉"这个位置是否还在窗口内"
这行代码对官方给出的三个样例
全部都能过（
"abcabcbb" /
"bbbbb" /
"pwwkew"），所以很容易以为自己写对了。
它在
"abba" 上会当场暴露。
6.1 "abba"：正确 vs 漏判据，逐帧对照
下表把两种写法并排放。
看第 4 步。
第 4 步是关键：
a 确实出现过（下标 0），但那个位置
已经被第 3 步的 left = 2 甩到窗口左边去了。它现在对"窗口内是否有重复"这件事
没有任何影响。
所以
left 必须
原地不动。
而漏判据的写法会算出
left = 0 + 1 = 1 ——
从 2 退回到 1。窗口变成
"bba"，里面有两个
b，不变量 1 破了，长度算成 3（虚高）。
6.2 再看一个："abcba"
正确答案
3，漏判据的写法会算出
4（窗口
[1,4] =
"bcba"，
b 重复）。
6.3 一句话记住
判据不是「这个字符出现过」，而是「它上次出现的位置还落在窗口里」。
代码里的两种等价表达：
# 直接写出来
if ch in last and last[ch] >= left:
left = last[ch] + 1
# 或者交给 max 拦
if ch in last:
left = max(left, last[ch] + 1)
"abcabcbb" 这种例子，你可以主动说一句：
"这题的关键判据是 last[ch] >= left。很多人只写 if ch in last，在 "abba" 上会让 left 倒退，答案从 2 变成 3。max(left, ...) 就是在拦这个倒退。"
这句话能直接把"背过模板"和"真懂"区分开。
七、另外两种写法，以及各自的坑
7.1 set + while 收缩：好理解，但常数大
def lengthOfLongestSubstring(s):
win = set()
left = 0
ans = 0
for right, ch in enumerate(s):
while ch in win: # 一步一步挪，边挪边删
win.remove(s[left])
left += 1
win.add(ch)
ans = max(ans, right - left + 1)
return ans
：非常直白 —— "窗口里重复了，就一点点把左边吐出来，直到不重复"。面试紧张时写这个更不容易出错。
缺点：左指针是
挪的，不是
跳的。虽然总复杂度仍是 O(n)（每个字符最多进出窗口一次），但要扫过更多中间状态，常数比
lastSeen 版大。
另外：这个写法里
left 不会倒退 —— 因为
while 循环只会让
left 增大。
它天然满足不变量 2，代价是牺牲了"一步跳到位"。
7.2 ASCII 数组：想快，但初始值必须是 -1，不能是 0
如果字符串只含 ASCII 字符，可以用长度 128（或 256）的数组代替哈希表：
def lengthOfLongestSubstring(s):
last = [-1] * 128 # ⚠️ 必须是 -1，不能是 0
left, ans = 0, 0
for right, ch in enumerate(s):
idx = ord(ch)
if last[idx] >= left:
left = last[idx] + 1
last[idx] = right
ans = max(ans, right - left + 1)
return ans
-1 是关键。如果图省事初始化成
0：
last = [0] * 128 # ❌
# 第一个字符就出事：last[idx] = 0 >= left = 0 → left = 0 + 1 = 1
# 窗口凭空跳过第一个字符，答案从 3 变成 2
因为
0 是一个
合法的下标，"没出现过"和"出现在下标 0"就分不清了。
用 -1 表示"没出现过"，才能让
last[idx] >= left 这个判据正确工作（
-1 >= 0 为假 ✓）。
同理，用哈希表时不能写 last.get(ch, 0) —— 那也是把"没出现过"当成"出现在 0"。要么用 ch in last 判断，要么用 last.get(ch, -1)。
7.3 存"下一个起点"的写法
还有一种很巧的变体 —— 表里存的不是"当前位置"，而是"
下一次该从这里开始的下标"：
def lengthOfLongestSubstring(s):
nxt = {} # 字符 -> 冲突时 left 应该跳到的位置
left, ans = 0, 0
for right, ch in enumerate(s):
left = max(left, nxt.get(ch, 0)) # 注意 get 的默认值是 0（= 不跳）
nxt[ch] = right + 1 # 存"右边界 + 1"
ans = max(ans, right - left + 1)
return ans
这样每轮都无条件
left = max(left, ...)，省掉了
if。
默认值用 0 —— 因为这里
0 的含义是"不用跳"，而不是"出现在下标 0"。（和 7.2 的坑刚好相反，注意区分两张表的语义。）
八、变体：同一个窗口，换一个"什么算合法"
滑动窗口的题可以按"
窗口要满足什么性质"分成两族。LC 3 是"最简单的那族"。
8.1 LC 159 / 340：至多 K 个不同字符
LC 340（至多 K 个不同字符的最长子串）：把"无重复"换成"窗口内不同字符数 ≤ K"。
结构完全一样，只把"窗口是否合法"的判断改成
计数：
def lengthOfLongestSubstringKDistinct(s, k):
if k == 0:
return 0
cnt = {} # 字符 -> 窗口内出现次数
left, ans = 0, 0
for right, ch in enumerate(s):
cnt[ch] = cnt.get(ch, 0) + 1
while len(cnt) > k: # 不同字符超了 → 收缩
cnt[s[left]] -= 1
if cnt[s[left]] == 0:
del cnt[s[left]]
left += 1
ans = max(ans, right - left + 1)
return ans
：
1. 判据从"某个字符 ≥ left"变成"
不同字符总数 > K"；
2. 所以收缩
必须用 while（可能要连缩好几格），不能一步跳 —— 因为"该跳到哪"没有一个现成的下标。
LC 159 是 K = 2 的特例，代码一样。
对比 LC 3：LC 3 能"一步跳"是因为冲突点只有一个明确的坐标（last[ch] + 1）。
8.2 LC 424：替换后的最长重复字符
LC 424：最多替换 K 个字符，求能得到的最长重复字符子串。
合法性判据变成一个不等式：
def characterReplacement(s, k):
cnt = {}
left, ans, maxCnt = 0, 0, 0
for right, ch in enumerate(s):
cnt[ch] = cnt.get(ch, 0) + 1
maxCnt = max(maxCnt, cnt[ch])
# 窗口长度 - 出现最多的那个字符的次数 = 需要替换的字符数
if right - left + 1 - maxCnt > k:
cnt[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
if 不是 while —— 窗口只会"跟着 right 一起长大"，不会缩回去。这是 424 特有的技巧（
maxCnt 只增不减，保证窗口长度单调不减）。
8.3 LC 76：最小覆盖子串 —— 方向反过来
前面几题都是求
最长，LC 76 求的是
最短的、但必须包含
t 的全部字符的窗口。
from collections import Counter
def minWindow(s, t):
need = Counter(t)
missing = len(t) # 还差多少个字符
left = 0
best = (0, 0)
bestLen = float('inf')
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0: # 窗口已经覆盖全部所需字符 → 尽情收缩
if right - left + 1 < bestLen:
bestLen = right - left + 1
best = (left, right)
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[best[0]:best[1] + 1] if bestLen < float('inf') else ''
：LC 3 是"窗口一有问题就修"，LC 76 是"窗口一合法就试着变小"。
同一个骨架，两个相反的目标。
8.4 其他两个近亲
8.5 变体关系总表
共同骨架：
right 扩张 → 检查合法性 → （可能）收缩
left → 更新答案。
分岔点只有一个：
"该收缩到哪里"有没有一个明确的坐标。LC 3 有（
last[ch] + 1），所以能一步跳；其它题没有，只能一格格缩。
九、Java 版
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] last = new int[128];
java.util.Arrays.fill(last, -1); // ⚠️ -1 不是 0
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (last[ch] >= left) {
left = last[ch] + 1; // 一步跳到重复字符的下一位
}
last[ch] = right;
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
：
- 数组初始值是
0，必须手动填 -1 —— Java 数组默认零值，而 0 是合法下标，会把"没出现过"误判成"出现在 0"。
char 可以直接当数组下标（自动转 int），不用 ord()。- 如果题目允许 Unicode 字符，
charAt 会拆开代理对（和 Python 的 s[i] 一样的问题）。稳妥做法是按 codePointAt 遍历，或者用 HashMap<Integer, Integer>。
十、边界情况与常见坑
常见坑
坑 1：判据漏掉 >= left（§6）⚠️ 最容易错
if ch in last:
left = last[ch] + 1 # ❌ left 会倒退
官方三个样例全过，
"abba" 立刻错（2 变成 3）。
坑 2：数组 / 哈希表初始值用 0（§7.2）
last = [0] * 128 # ❌ 第一个字符就被"假重复"顶掉
用
-1。或者用
last.get(ch, -1)。
坑 3：把"最长子串"当成"最长子序列"
"pwwkew" 的
"pwke" 长度 4 是子序列，不是子串。题目要连续。
坑 4：忘记更新 last[ch] = right
即使这一步构成重复、
left 已经跳过了，
当前这个 right 仍然要记进去（它才是最新位置）。漏掉的话下一次遇到同一个字符会跳到过期的位置。
坑 5：ans 更新时机
一定要在
处理完 left 之后再算
right - left + 1。如果先算再收缩，会算出一个"还没修好的窗口"的长度。
坑 6：空串 / 单字符
"" → 0，
"a" → 1。循环天然处理，但要有心理准备（这题答案可以为 0，不是"至少一个字符"）。
坑 7：s[i] 拆开 emoji
Python 里
s[i] 按 UTF-16 码元切，
"😀" 会被拆成两个代理项，于是"同一个字符"被当成"两个不同字符"，答案偏大。要按码点遍历（
for ch in s 就是按码点 ✓，但
s[i] 不是）。
判断方法：
s = "😀😀"
len(s) # 4 ← 按码元
len(set(s)) # 2 ← 错！其实是 1 个字符
# 正确：len(set(list(s))) 或直接用 for ch in s
边界情况表
十一、面试怎么答
第一步：先给结论和复杂度
"滑动窗口。右指针一路扩张，把字符吃进窗口；遇到窗口内重复就让左指针跳过那个重复位置。两个指针都只往右走，所以是 O(n)，空间 O(min(n, 字符集))。"
第二步：主动说清维护什么
"维护一张表记每个字符最后出现的下标，而不是一个 set。这样左指针能一步跳到 last[ch] + 1，不用一格格挪。"
第三步：主动说清判据（这是最关键的一句）
"判据是 last[ch] >= left —— 不是"这个字符出现过"，而是"它上次出现的位置还在窗口里"。因为某个字符可能很久以前出现过、但已经被甩到窗口左边去了，那种情况不构成重复。写成 if ch in last 就会让左指针倒退。"
第四步：主动给反例
"比如 "abba"：走到最后一个 a 时，last['a'] = 0，但 left 已经是 2 —— 这个 0 在窗口外，left 不该动。如果写成无条件跳，left 会退到 1，窗口变成 "bba"，答案错算成 3。"
第五步：如果被追问"为什么左指针不能倒退"
"因为不变量的根基是'窗口内无重复'。左指针后退会把之前挤出去的字符又放回来，窗口里立刻出现重复，之后所有长度都是虚高的。"
如果被追问"能不能不用哈希表"：
"如果限定 ASCII，可以用长度 128 的数组，把哈希换成数组下标，常数更小。但初始值必须填 -1 —— 填 0 的话，'没出现过'和'出现在下标 0'就分不清了，第一个字符就会被误判成重复。"
如果被追问"还有别的写法吗"：
"有。用 set 加 while 循环一格格收缩，更好理解，总复杂度也是 O(n)，但常数大一些。它的好处是天然不会倒退 —— 因为 while 只会让 left 增大。"
最后一句收尾（体现你见过变体）：
"这个骨架能直接推到 340（至多 K 个不同字符）和 76（最小覆盖子串）。分岔点在于'该收缩到哪里'有没有一个明确的坐标 —— LC 3 有（last[ch] + 1），所以能一步跳；340 和 76 没有，只能 while 一格格缩。"
结语
LC 3 通常被当成"滑动窗口的第一题"，但它其实埋了一个很值得琢磨的点：
判断"要不要动左指针"时，问的不是"这个字符见过吗"，而是"它还在窗口里吗"。
这个区别在官方样例里完全看不出来 —— 三个样例都是"重复字符就在窗口内"的情况，所以你写漏了也能全过。只有
"abba" /
"abcba" 这种"旧位置已经被甩出去"的串才会暴露。
而它背后是滑动窗口最根本的一条约束：
左指针只能往右走。 一旦回头，"窗口内无重复"这个不变量就破了，后面所有结论都不成立。
下次写滑动窗口的题，先问自己两个问题：
- 窗口要满足什么性质？（无重复 / 不同字符数 ≤ K / 覆盖某集合）
- 这个性质被破坏时，左指针该跳到哪里？ 有明确坐标就能一步跳，没有就老实
while。
回答完这两句，代码基本就出来了。
系列导航：本文是「暑期面经汇总」算法系列的第 14 篇，也是第一篇字符串 / 滑动窗口题。前作：LC 206 反转链表 · LC 21 合并两个有序链表 · LC 23 合并 K 个升序链表 · LC 141/142 环形链表 · LC 19 删除链表倒数第 N 个节点 · LC 143 重排链表 · LC 234 回文链表 · LC 160 相交链表 · LC 82 删除排序链表中的重复元素 II · LC 102 二叉树的层序遍历 · LC 236 二叉树的最近公共祖先 · LC 124 二叉树中的最大路径和 · LC 104/226 二叉树的最大深度 & 翻转二叉树。