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

给一个字符串，找出里面最长的一段、要求这一段里没有重复的字符，返回它的长度。题目（出处：力扣 3 题面）给的第一个例子是 "abcabcbb"，答案是 3，对应 "abc" 这一段。第二个例子 "bbbbb"，答案是 1。第三个例子 "pwwkew"，答案是 3，对应 "wke"。题目还特意提醒了一句，"pwke" 是子序列，不是子串，所以不算。

子串和子序列这两个词，我一开始是混着用的。这道题把它们分得很清楚：子串必须是连着的一段，中间不能跳；子序列可以跳着挑。"pwwkew" 里 p、w、k、e 各挑一个能凑出 "pwke"，长度 4，比答案 3 还长，但它不连着，所以不算。答案只在连着的段里找，这个限制反而让题目变简单了，因为连着的段有个好处：一段里有没有重复字符，只取决于这段本身，跟它外面的字符没关系。

最笨的办法：所有子串都数一遍

我最先想到的办法特别直接：把所有可能的子串一个一个列出来，每个都检查一遍有没有重复字符，长度取最大。

def longest_naive(s):
    best = 0
    n = len(s)
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

从位置 i 出发往后扫，扫到重复就停，这个子串就是从 i 出发最长的无重复子串；对每个 i 都这么干一遍，取最大，答案肯定是对的。问题是它做了太多重复劳动：从 i 出发扫过的字符，从 i+1 出发又要扫一遍。最坏的情况是整个字符串一个重复都没有，比如 5000 个全不重复的字符，那每个起点都要扫到字符串末尾，总共差不多 1250 万次操作。我本地跑了一下，5000 个全不重复的字符（汉字字符，从 U+4E00 起连续取 5000 个），这个写法用了 5.5399 秒。答案 5000 是对的，就是等得人难受。

其实这个写法已经比真正的暴力好一点了：真正的暴力是把每个子串都完整检查一遍，内层还要再套一层循环。我这个版本从每个起点出发扫到重复就停，重复劳动少了一些，但还是慢。慢的原因没变：不同的起点会把同一个字符反复扫过。

窗口的想法：右端只往前，左端只在重复时跳

不用枚举所有子串，只需要维护一段“当前”的无重复子串，让它一直往前滑。右端一个字符一个字符往前走，左端站在当前这段的开头。右端每进来一个新字符，只有两种可能：它不在当前这段里，那这段就变长一格；它已经在当前这段里了，那这段就不能再留着旧的那个它，左端必须跳到旧的那个它之后。

跳到“旧的那个它之后”这一步，靠一个哈希表：表里记每个字符上次出现的位置。右端走到一个字符，看一眼表里它上次出现的位置，左端直接跳到那个位置加一。跳过去的那一段就扔了，不用一个一个往右挪。

def longest_window(s):
    last = {}      # 字符 -> 上次出现的位置
    best = 0
    left = 0       # 窗口左端，窗口是 s[left:right+1]，里面没有重复字符
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1   # 左端跳到上次出现位置之后
        last[ch] = right
        best = max(best, right - left + 1)
    return best

左端敢一下子跳这么远，是因为跳过去的那一段里，旧的那个重复字符还在里面。只要它还在，窗口里就有两个相同的字符，肯定不合法；跳到它之后，窗口里就只剩新的这一个，合法了。而且跳过去的那一段里不可能藏着更长的无重复子串。任何从那一段里开始的子串，右端最多走到当前这个字符之前就撞上重复，而当前窗口从跳后的左端开始、右端走到当前位置，长度只会比它更长。

拿官方第一个例子走一遍。字符串是 "abcabcbb"。开头三个字符 a、b、c 都没重复过，窗口是 [0:2]，也就是 "abc"，长度 3。到位置 3 又出现一个 a，它上次在 0，左端跳到 1，窗口变成 "bca"。再往后，位置 4 的 b 上次在 1，左端跳到 2，窗口变成 "cab"；位置 5 的 c 上次在 2，左端跳到 3，窗口又回到 "abc"。位置 6 再撞上 b，它上次在 4，左端跳到 5，窗口缩成 "cb"，长度 2。最后一个 b 上次在 6，左端跳到 7，窗口只剩 "b"，长度 1。

这个写法每个字符只处理一次，哈希表查找平均 O(1)，所以是 O(n) 时间。表里最多存下所有出现过的不同字符，额外空间 O(n)，更准确说是 O(min(n, 字符集大小))。

一个容易写错的地方：左端不能往回跳

上面代码里有个条件我一开始没写：last[ch] >= left。我第一版写的是只要字符在表里出现过，左端就跳到它上次出现位置加一。跑 "abba" 的时候就错了：答案应该是 2，对应 "ab" 或者 "ba"，我那版算出来是 3。

问题出在最后一个 a。它上次出现在位置 0，但这时候窗口的左端已经在 2 了，窗口是从 "bb" 里第二个 b 开始的那一段。a 上次出现的位置 0，左端早就跳过去了，不在窗口里。如果左端听它的，跳到 0 加 1，也就是 1，窗口就变成了 "bba"，b 出现了两次，窗口本身就不合法，算出来的长度 3 也是错的。

所以左端跳之前，要先看这个重复字符的上次出现位置还在不在窗口里面。在里面，才跳；已经在外面了，就当没看见，窗口不动。这个条件写成 last[ch] >= left，也可以写成跳的时候取 max(left, last[ch] + 1)，是一个意思。last 表里存的是全串的上次出现位置，不管它在不在窗口里；窗口的左端只往右走，不回头，这条规矩得守住。

空字符串要单独想一下：循环一次也不跑，best 保持 0，返回 0。只有一个字符的字符串，窗口就是它自己，长度 1。"bbbbb" 这种全是同一个字符的，右端每走一步左端就跟着跳一步，窗口永远长度 1，答案 1。"dvdf" 这个例子也值得走一遍：右端走到第二个 d 的时候，d 上次在 0，左端跳到 1，窗口是 "vdf"，长度 3，答案 3。"tmmzuxt" 答案是 5，对应 "mzuxt"，左端在第二个 m 出现时跳到第一个 m 之后。

我拿什么验的

官方的三个例子都过了："abcabcbb" 得 3，"bbbbb" 得 1，"pwwkew" 得 3。然后我写了 3000 组随机数据（种子 20261110，长度 0 到 30，字母表只有 a、b、c、d、e 这五个字母，故意让重复多一点），把正式解法的结果和最笨的解法逐个对，失配是 0 组。边界也顺手测了："" 是 0，" " 是 1，"aa" 是 1，"abba" 是 2，"tmmzuxt" 是 5，"abcde" 是 5，"aaaaabbbbb" 是 2。

速度上也对得上。5000 个全不重复的字符那组，最笨的写法 5.5399 秒，窗口写法 0.0022 秒，答案都是 5000，差了两千多倍。长度 2000 的循环字母串（a 到 z 循环），最笨的写法 0.0287 秒，窗口写法 0.0007 秒，答案都是 26。长度 100000 的随机小写字母串（种子 7），最笨的写法 0.2309 秒，窗口写法 0.0340 秒，答案都是 19。

回头看，左端为什么可以跳、又为什么不能往回跳，想通这两点是这道题真正要过的地方，代码本身只有十来行。最笨的写法图个安心，每个起点都扫一遍；窗口写法先想清楚一件事：从左端开始、到右端为止的这一段，如果里面没有重复，那它就是以右端结尾的最长无重复子串；如果有重复，左端跳到重复字符上次出现之后，得到的还是以右端结尾的最长无重复子串。右端扫完一遍，所有位置的最长情况都数过了，答案就是其中最大的那一个。哈希表在这里存的是每个字符上次出现的位置，没有这个位置，左端就不知道该跳到哪。

doocs/leetcode 的 0003 题解里一共四个方法，暴力枚举、滑动窗口逐个移左端、哈希表优化、数组桶代替哈希表，都是同一条思路的不同写法。正式解法和其中哈希表优化那个方法结构相同，"abba" 这种左端不能回跳的情形在它的示例里有专门说明。对下来没有遗漏的情形。