无重复字符的最长子串 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

示例 1

输入：s = "abcabcbb"

输出：3（最长子串是 "abc"）

示例 2

输入：s = "pwwkew"

输出：3（最长子串是 "wke"）

💭 模拟答题者思考

1. 暴力：枚举所有子串再判断是否有重复，O(n³) 或 O(n²)。

2. 重复在哪？right 右移时，其实只有「新加入的字符」可能造成重复。

3. 用滑动窗口：right 不断右扩，一旦 s[right] 在窗口内出现过，就把 left 跳过去。

4. 关键：记录每个字符最近的下标，跳 left 时只能往右（用 max/判断 last[c] >= left），不能倒退。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`left`	int	定义：当前无重复窗口的左边界维护：窗口 [left, right] 内永远无重复字符更新：遇到重复字符时，跳到该字符上次出现位置的右侧
`last[c]`	map<char,int>	定义：字符 c 最近一次出现的下标维护：随扫描实时更新更新：每轮 last[s[right]] = right
`ans`	int	定义：无重复子串的最大长度维护：所有合法窗口长度的最大值更新：ans = max(ans, right - left + 1)

⌨️ 落码步骤

1. last = {}，left = 0，ans = 0

2. 遍历 right：若 s[right] 在 last 中且 last[c] >= left，则 left = last[c] + 1

3. 更新 last[s[right]] = right

4. ans = max(ans, right - left + 1)

💻 代码实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}   # 字符 -> 最近一次出现的下标
        left = 0    # 当前窗口左边界
        ans = 0
        for right, c in enumerate(s):
            if c in last and last[c] >= left:
                left = last[c] + 1   # 左边界跳到重复字符右侧
            last[c] = right
            ans = max(ans, right - left + 1)
        return ans

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> last;  // 字符 -> 最近下标
        int left = 0, ans = 0;
        for (int right = 0; right < (int)s.size(); right++) {
            char c = s[right];
            auto it = last.find(c);
            if (it != last.end() && it->second >= left)
                left = it->second + 1;
            last[c] = right;
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
// 时间 O(n)，空间 O(|Σ|)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(|Σ|)

⚠️ 常见坑

❗ 跳 left 前必须判断 last[c] >= left：字符虽出现过但若在窗口左侧之外，不能把 left 往回拉。

❗ 先跳 left 再更新 last[c]，顺序不能反。

❗ 窗口长度是 right - left + 1，不要漏掉 +1。

🔍 必测边界 Case

Case 1：空串

s = "" → 0

Case 2：全相同

s = "bbbb" → 1