求最长无重复字符子串的长度。

核心回答

用滑动窗口加字符最近出现位置表，维护一个没有重复字符的连续区间。右端逐个加入字符；如果这个字符上一次出现在当前窗口内，就把左端移到上次位置之后，再更新最大长度。

关键是左端只能前进：left = max(left, 上次位置 + 1)。这样既能去掉当前重复，又不会因为遇到窗口外的旧字符而退回。哈希表操作按平均常数时间计算，整体时间为 O(n)，额外空间为 O(min(n, 字符集大小))。

题目求的是连续的子串长度。例如 pwwkew 的答案为 3，wke 连续且无重复；pwke 虽然无重复，却不是连续子串。

Python 实现

def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        left = max(left, last_seen.get(char, -1) + 1)
        last_seen[char] = right
        best = max(best, right - left + 1)

    return best

last_seen 记录字符在已经扫描部分中最近一次出现的位置，不只记录当前窗口；因此移动左端时需要取 max。没有出现过的字符使用 -1，得到的候选左端是 0。

这里按 Python 字符串的 Unicode 码点处理，字典不限定为 128 个 ASCII 字符。输入是 str；若输入为字节流，应先按正确编码解码。

为什么遇到重复时这样移动

处理 right 前，当前窗口内的字符互不重复。新字符若上次位于 previous，有两种情况：

• previous < left：旧字符已在窗口外，不影响当前窗口，左端保持原位。
• previous >= left：要排除旧字符，新的合法窗口必须从 previous + 1 或更靠右开始；取恰好这个位置，可以保留尽量长的合法区间。

因此每处理一个右端，都得到以它结尾的最长无重复窗口；遍历所有右端并取最大值，就覆盖了全局最优答案。

abba 能检查左端回退这个常见错误：读到第二个 b 时，左端移动到下标 2；最后读到 a，它上次在下标 0，已经在窗口外，所以左端仍应为 2。若直接赋值为 1，就会把 bba 错算成合法窗口。

复杂度和实现细节

右端恰好扫描 n 次，每步只做字典读写和常数次比较，不会重新扫描整个窗口，因此在哈希操作平均 O(1) 的条件下，时间为 O(n)。字典最多保存输入中出现过的不同字符，空间为 O(min(n, 字符集大小))。

另一种写法是维护窗口内字符计数，重复时用 while 逐个移出左端字符；两个指针都只前进，总移动次数仍为 O(n)。若在每一步切片并重新构造集合检查整段窗口，就会增加扫描和复制成本，不能再直接沿用这个复杂度。

边界样例

assert length_of_longest_substring("") == 0
assert length_of_longest_substring("a") == 1
assert length_of_longest_substring("aaaa") == 1
assert length_of_longest_substring("abba") == 2
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("你好你世") == 3
assert length_of_longest_substring("🙂a🙂") == 2

空格和标点也是字符。若需求按用户看到的字形计算，例如组合音标或由多个码点构成的表情，应先明确规范化与字素分割规则；本实现比较码点，不会自动把这些序列当成一个字符。

常见追问

怎样返回具体子串？ 更新 best 时同时保存起点，结束后只切片一次。若多个子串同样长，可以按约定保留最早出现的一个。

为什么不能排序后去重？ 排序会破坏原字符串的连续性；去重得到不同字符总数，也无法反映它们能否共同位于某个连续区间。

参考资料