算法 - 无重复字符的最长子串

Posted on

1. 题目

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

注意「子串」是连续的，区别于「子序列」。

示例:

1
2
3
4
5
6
7
8
9
10
输入: s = "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，长度为 3。

输入: s = "bbbbb"
输出: 1

输入: s = "pwwkew"
输出: 3
解释: 最长子串是 "wke"，注意 "pwke" 是子序列不是子串。

2. 解题思路

标准的滑动窗口问题。维护一个窗口 [left, right]，保证窗口内始终无重复字符。

用 Map<字符, 最近一次出现的下标> 记录每个字符最后出现的位置。右指针 right 逐个字符向右扩展：

  • 如果 s[right] 之前出现过，且其位置在窗口内（>= left），说明加入它会重复，于是把 left 直接跳到「重复字符上次位置 + 1」，一步到位，无需逐个收缩。
  • 更新 s[right] 的位置为 right。
  • 每一步用 right - left + 1 更新最大长度。

关键技巧：left 只能右移不能回退，所以要取 Math.max(left, lastPos + 1)，避免像 abba 这类用例把 left 拉回左边。

  • 时间复杂度：O(n)，每个字符最多被访问一次。
  • 空间复杂度：O(min(n, 字符集大小))。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function lengthOfLongestSubstring(s: string): number {
    const lastPos = new Map<string, number>();
    let left = 0;
    let maxLen = 0;

    for (let right = 0; right < s.length; right++) {
        const ch = s[right];

        // 字符在窗口内出现过，left 跳到重复处之后
        if (lastPos.has(ch)) {
            left = Math.max(left, lastPos.get(ch)! + 1);
        }

        lastPos.set(ch, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

// 测试
console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("bbbbb"));    // 1
console.log(lengthOfLongestSubstring("pwwkew"));   // 3
console.log(lengthOfLongestSubstring("abba"));     // 2

4. 面试延伸

  • 不用 Map 的写法？ 字符集有限（如 ASCII）时用长度为 128 的数组更快；也可用 Set 记录窗口内字符，重复时循环删除 s[left++] 直到不重复。
  • 变形题：至多包含两个不同字符的最长子串（LeetCode 340）、最小覆盖子串（76） 都是滑动窗口的进阶，套路一致：右扩满足条件、左缩优化答案。
  • 记住模板：for right + while 违反条件 then left++，能覆盖绝大多数子串类题目。

难度：中等 | LeetCode 3 题 | 滑动窗口入门必刷