Longest Substring Without Repeating Characters

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

返回最长无重复字符子串的长度。这是学习滑动窗口最经典的一题，重点是窗口一旦失效就收缩，而不是重新开始。

StringSliding Window

题目定位

题目要求连续子串，窗口失效的唯一原因是内部出现重复字符，因此“失效就收缩”的滑动窗口是最自然的解法。

关键观察

一旦字符重复，唯一能恢复合法性的动作就是右移左边界，别的操作都无法解决问题。

目标复杂度

O(n) / O(k)

这题的解法思路怎么拆

用一个 set 维护当前窗口里有哪些字符。

右指针每次向右扩一个字符。

如果新字符已经在窗口里，就不断移动左指针，直到重复字符被移出。

窗口重新合法后，再更新最长长度。

拿一个例子顺一遍

例如 s = "abcabcbb"。

窗口先扩成 "abc"，此时答案更新为 3。

当第二个 'a' 到来时，左指针持续右移，把前一个 'a' 移出去，再继续扩张。

后面没有任何合法窗口长度超过 3，所以最终答案仍是 3。

参考实现

Python

def lengthOfLongestSubstring(s: str) -> int:
    seen = set()
    left = 0
    best = 0

    for right, char in enumerate(s):
        while char in seen:
            seen.remove(s[left])
            left += 1

        seen.add(char)
        best = max(best, right - left + 1)

    return best

TypeScript 版本

TypeScript

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right += 1) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left += 1;
    }

    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }

  return best;
}