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

Origin: LeetCode 3

题目描述

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

示例 1： 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”。

示例 2： 输入: s = “bbbbb” 输出: 1

示例 3： 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”。注意答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10
• s 由英文字母、数字、符号和空格组成

我的解法

function lengthOfLongestSubstring(s: string): number {
    if (!s.length) return 0
    const set = new Set<string>()
    let left = 0
    let maxLength = 0
    for (let right = 0; right < s.length; right++) {
        while (set.has(s[right])) {
            set.delete(s[left])
            left++
        }
        set.add(s[right])
        maxLength = Math.max(maxLength, set.size)
    }
    return maxLength;
};

8 组用例实际验证通过，含三个经典坑："dvdf"（left 回退陷阱）、"abba"（重复字符在窗口左边界外）、"tmmzuxt"（重复字符已被移出窗口）。

亮点：Math.max(maxLength, set.size) 直接用 set.size 记录窗口大小，省掉了 right - left + 1 的区间计算——set 本身就是窗口内容的真实记录，窗口信息被自然复用。

解题思路（草稿）

滑动窗口——标准解法

窗口 [left, right] 内维护”无重复”这个不变量。right 每前进一格，如果新字符造成重复，left 收缩到重复字符消失为止。

function lengthOfLongestSubstring(s: string): number {
    const window = new Set<string>()
    let left = 0, maxLen = 0
    for (let right = 0; right < s.length; right++) {
        const c = s[right]
        while (window.has(c)) {
            window.delete(s[left])
            left++
        }
        window.add(c)
        maxLen = Math.max(maxLen, right - left + 1)
    }
    return maxLen
}

关键点：

1. 不变量：窗口内永远无重复。right 扩张可能破坏它，left 收缩恢复它。
2. left 只前进不后退：这是滑动窗口 O(n) 的原因。right 走 n 步，left 最多也走 n 步，总操作 2n。
3. Set 存的是什么：当前窗口内的字符。window.has(c) 判断的就是”新字符是否已在窗口里”。

暴力对照

暴力是枚举所有子串 O(n²) 每个子串再查重 O(n)，共 O(n³)。滑动窗口的本质优化：重复的子串不再重新检查——[left, right-1] 无重复这个信息被复用了。

手推一遍 “abcabcbb”

right=0 'a': 窗口{a}        max=1
right=1 'b': 窗口{a,b}      max=2
right=2 'c': 窗口{a,b,c}    max=3
right=3 'a': 重复！删 a，left=1   窗口{b,c,a}
right=4 'b': 重复！删 b，left=2   窗口{c,a,b}
right=5 'c': 重复！删 c，left=3   窗口{a,b,c}
right=6 'b': 重复！删 a,删 b，left=5  窗口{c,b}
right=7 'b': 重复！删 c,删 b，left=7  窗口{b}
max = 3

注意 left 收缩是逐个删，不是跳到目标位置——所以最坏还是 O(2n)，均摊 O(1)。

优化变体：left 直接跳跃

用 Map 记每个字符最后出现的位置，left 可以直接跳：

const map = new Map<string, number>()
// ...left = Math.max(left, map.get(c)! + 1)

但要注意 max 取旧位置的情况（字符在窗口外），需要 Math.max 防止 left 后退。Set 版逻辑更简单，面试写 Set 版足够。

复杂度

• 时间：O(n)，left/right 各最多走 n 步
• 空间：O(min(n, 字符集大小))，窗口最多装下不重复的字符

关联

• 滑动窗口 - 模板总结
• 438. 找到字符串中所有字母异位词 - 同模板的下一题
• 76. 最小覆盖子串 - 滑动窗口困难版