无重复字符的最长子串

先想笨办法 · 暴力枚举：最直白的笨办法：外层枚举每个起点 i，内层从 i 往右一格一格铺到 j，每铺一段就检查里面有没有重复，取最长的合法段。一共 O(n²) 段，慢在这两层循环上。

笨办法浪费在哪：关键浪费：起点 i 每往右挪一位，右边那一截就从头重新铺、重新查重。可上一段已经知道「到哪重复」了，左端其实只需往右走、永不回退。把这层重复劳动省掉，就自然变成了滑动窗口。

于是维护一个窗口 [l, r]：右指针 r 一直往右把新字符吃进窗口；一旦窗口里出现重复，就移动左指针 l 把左边挤出去，直到不再重复。左端只进不退，省掉了暴力解那层重铺，窗口里随时都是「无重复的一段」。

准备：用一个集合记下「窗口里现在有哪些字符」，只记字符本身、不记下标，方便判断有没有重复。

r = 0 · 吃进 p：p 不在集合里，放心吃进来。窗口 = "p"，当前最长 = 1。

r = 1 · 吃进 w：w 也不在集合里，吃进来。窗口 = "pw"，最长更新为 2。

r = 2 · 又遇到 w：想吃进 2 号位的 w，可集合里已经有 w 了——重复！这时不能直接放，得先收缩左边。

r = 2 · 收缩①：把窗口最左边的 p 移出集合，l 前进到 1。但集合里还有 w，仍然和要吃的 w 重复，继续收缩。

r = 2 · 收缩②：再把 1 号位的 w 也移出集合，l 到 2。现在集合空了，不再有 w 了。

r = 2 · 吃进 w：现在可以把这个 w 吃进来了。窗口 = "w"，长度 1，没超过之前的最长 2。

r = 3 · 吃进 k：k 不在集合，吃进来。窗口 = "wk"。

r = 4 · 吃进 e：e 不在集合，吃进来。窗口 = "wke"，长度 3，刷新最长记录！

r = 5 · 又遇到 w：又想吃 w，但集合里有 w，重复。收缩左边。

r = 5 · 收缩：把 2 号位的 w 移出集合，l 到 3。集合里没有 w 了。

r = 5 · 吃进 w：吃进 w，窗口 = "kew"，长度 3，没超过最长。

结束：r 走到头。整个过程中窗口最长是 3（"wke"），这就是答案。

滑动窗口能套很多题：最小覆盖子串、长度最小子数组、字母异位词……记住「窗口伸缩」这个手感。

边界三连：三种小输入先心里跑一遍：空串、全相同、以及 abba 这种「左指针差点回退」的样例。

面试追问：无重复字符的最长子串 的三个高频追问：复杂度怎么推、空间多大、以及「一步跳」的进阶写法。

「右扩、不合法就左缩」是所有连续子串/子数组题的骨架：LC209 长度最小子数组（和 ≥ target 时缩）、LC76 最小覆盖子串、LC438 找异位词（定长窗口）——只换「合法条件」。看 最小覆盖子串图解 接着练，写不出来就问问 AI 助教小欧。