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

题目描述

在字符串 s 中找一段连续且没有重复字符的片段，返回它的最大长度。子串不能跳过中间字符；空字符串的答案为 0。

输入输出示例

示例 1

"abcabcbb" → 3，例如 "abc"；"bca" 和 "cab" 也正确。

示例 2

"bbbbb" → 1。任意相邻的两个字符都重复，只能取一个 "b"。

示例 3

"pwwkew" → 3，可取 "wke" 或 "kew"。"pwke" 跳过了一个 w，是子序列，不是本题要求的子串。

输入约束

字符串长度为 0–10⁵。
s 由英文字母、数字、符号或空格组成。

方法一：滑动窗口 + 哈希表

核心思想：毛毛虫爬行（滑动窗口）

想象一个字符串是一条长长的叶子，你要找到叶子上最长的一段没有相同标记的区域。
我们可以养一条“毛毛虫”，它的右端（j）不断向前伸去吃新叶子，左端（i）在被咬到重复叶子时向前缩。这条毛毛虫的身体（窗口）就是当前无重复字符的子串。

角色设定（变量含义）

j (右指针/毛毛虫头部)：负责向前探索，遍历字符串的每一个字符。
i (左指针/毛毛虫尾部)：负责划定窗口的左边界。注意，题解中的区间是 [i+1, j]，所以 i 指向的是当前窗口左边的前一个位置（或者说是上一个重复字符的位置）。
dic (哈希表/小本本)：用来记录每个字符最后一次出现的索引位置。相当于毛毛虫的“记忆”，遇到字符就知道之前在哪见过。
res (结果)：记录毛毛虫历史上最长的身体长度。

动作拆解（一步步怎么做）

头部向前吃 (j 遍历)：j 从 0 开始，一个一个往后读取字符 s[j]。
翻看小本本 (dic)：每吃到一个字符，就查一下小本本 dic，看看这个字符之前是不是刚吃过（在当前窗口内有没有重复）。
更新尾巴 (i 移动)：如果吃到了重复字符，尾巴 i 必须缩回来，保证窗口里没有重复。
- 这里有句核心代码：i = max(dic[s[j]], i)。
- 大白话解释：尾巴 i 要跳到“这个字符上次出现的位置”。但是！尾巴只能往前缩，不能往后退。所以要用 max，在“上次出现的位置”和“当前尾巴位置”里选最大的那个。
- （举个栗子：如果重复的字符在尾巴左边（早就滑出去了），那就不用缩，保持 i 不变即可）
记录新字符位置：把小本本更新，记下当前字符 s[j] 的新位置（覆盖旧的）。
量身体长度 (res 更新)：每次头部往前吃一步，就量一下当前毛毛虫有多长：j - i，并和历史最大长度 res 比较，保留最大的。

代码实现

下面四种语言都用 i 记录窗口左侧被排除的位置，用 dic 保存字符最近出现的下标。遇到重复字符时取较大的边界，保证 i 不会后退。

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        res = 0
        i = -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 哈希表记录
            res = max(res, j - i) # 更新结果
        return res

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1;
        int res = 0;
        int len = s.length();
        for (int j = 0; j < len; j++) {
            if (dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> dic;
        int i = -1;
        int res = 0;
        int len = s.size();
        for (int j = 0; j < len; j++) {
            if (dic.find(s[j]) != dic.end())
                i = max(i, dic.find(s[j])->second); // 更新左指针
            dic[s[j]] = j; // 哈希表记录
            res = max(res, j - i); // 更新结果
        }
        return res;
    }
};

JavaScript

var lengthOfLongestSubstring = function(s) {
    const dic = new Map();
    let i = -1;
    let res = 0;
    const len = s.length;
    for (let j = 0; j < len; j++) {
        if (dic.has(s[j]))
            i = Math.max(i, dic.get(s[j])); // 更新左指针 i
        dic.set(s[j], j); // 哈希表记录
        res = Math.max(res, j - i); // 更新结果
    }
    return res;
};

动画演示

点击“下一步”，观察毛毛虫怎样伸头、查小本本、缩尾巴、记位置，再量一量身体。绿色身体表示当前窗口；遇到重复时，相关叶片会标出“重复”，去重后才比较最长长度。i 标记的是窗口左侧被排除的位置，身体从 i + 1 开始。

毛毛虫的叶子旅行

建立解题类建立 Solution，准备演示场景

小本本 dic

a—未记录

b—未记录

c—未记录

✦ 最长成长记录—片叶子

当前窗口 ""i = — · j = — · 长度 0

速度步骤 1 / 44

方法二：动态规划 + 哈希表

状态定义与转移方程

悬停在段落上，浮动查看对应图示；也可点击或用键盘聚焦，按 Esc 收起。

动态规划示意图s = abcabcbb · j = 3

dp[j] ={

dp[j−1] + 1当 dp[j−1] < j−i

j−i当 dp[j−1] ≥ j−i

dic（读取前）{ a: 0, b: 1, c: 2 }

tmp：3 → 3res：3

dp[3] = 3：以 s[3] 结尾的最长无重复子串是 “bca”。

处理第一个字符时，前一步长度按 0 计算，无需访问实际的 dp[−1]。

状态压缩

哈希表记录

观察转移方程，关键问题是：每轮遍历字符 s[j] 时，如何得到它上次出现的位置 i？

用糖葫芦理解动态规划

这题要找的是最长无重复子串。方法二将动态规划、哈希表和状态压缩结合起来：先推导“以当前位置结尾”的最长长度，再记录所有位置中的最好成绩。下面用串糖葫芦的比喻，把这些概念连起来。

🍡 比喻场景：串糖葫芦

想象面前有一排不同口味的水果，你要从中取出连续的一段，串成一根口味不重复的糖葫芦。

字符串 s：面前的一排水果，例如 a b c a b c b b，相同字母代表相同口味。
子串：必须连着拿的几颗水果，不能跳过中间的一颗。
最长无重复子串：在所有连续取法中，找到口味互不重复、颗数最多的一串。

我们从左到右逐颗处理水果。每处理一颗，都先算出“必须以这颗水果收尾时，最多能串多长”，再看看是否刷新了历史纪录。

🔍 专业概念的大白话翻译

1. 状态定义 dp[j]：以当前水果收尾的最好成绩

专业说法：dp[j] 表示以字符 s[j] 为结尾的最长无重复子串的长度。

大白话：“我刚拿到下标为 j 的水果，而且必须把它作为最后一颗，此时这根糖葫芦最多能有多长？” 下标从 0 开始，所以 j = 3 指的是第 4 颗水果。

这里的“必须以它结尾”很关键：dp[j] 只记录当前结尾的最好成绩，不代表此前所有位置的历史最高纪录。

2. 哈希表 dic：记住每种口味上一次出现的位置

专业说法：使用哈希表记录各字符最后一次出现的索引位置。

大白话：“拿个小本本，记下每种水果上一次摆在哪里。” 再次遇到同一种口味，就覆盖它的旧位置；查不到时，用 -1 表示此前没有出现过。

小本本保存的是历史位置，即使那颗水果已经不在当前这一串里，记录也不必删除。

3. 转移方程：判断新水果能不能直接接上

处理 s[j] 时，先找到它上一次出现的位置 i。前一串长度是 dp[j-1]，占据的区间是 [j - dp[j-1], j-1]。比较前一串长度与两次相同口味之间的距离 j - i，就能判断是否冲突。

情况一：没出现过，或者旧水果已经在前一串之外。

判断条件：dp[j-1] < j - i。
大白话：前一串里没有这种口味，可以直接接上当前水果。
更新结果：dp[j] = dp[j-1] + 1。

例如处理 abba 的最后一个 a 时，前一串只有下标 2 的 b，长度是 1；旧 a 在下标 0，距离为 3 - 0 = 3。因为 1 < 3，接上后得到 ba，长度为 2。

情况二：撞口味了，旧水果就在前一串里面。

判断条件：dp[j-1] >= j - i。
大白话：不能把前一串原封不动地接长。必须去掉旧的同口味水果 s[i] 以及它左侧的部分，保留从 i+1 到 j 的连续一段。
更新结果：dp[j] = j - i，因为这段的颗数是 j - (i+1) + 1。

例如处理 abca 的最后一个 a 时，前一串是 abc，长度为 3；旧 a 在 i = 0，当前 j = 3。因为 3 >= 3，去掉旧 a 后保留 bca，长度仍为 3。注意，j - i 是下标之差，不是两段子串的长度之差。

当字符从未出现过时，i = -1，因此 j - i = j + 1。前一步最多只有 j 颗水果，必然满足 dp[j-1] < j - i，所以“首次出现”可以直接合并到情况一，无需再写一个分支。处理第一个字符时，前一步长度按 0 计算。

使用 dp 数组的解法

先把每个位置的成绩完整记下来：创建长度为 N 的数组 dp，依次计算每个 dp[j]。这样就能直接看到转移方程中的“前一步”和“当前步”。

先查询旧位置 i，再把当前下标 j 写入哈希表。
用 prev 读取前一步长度：当 j > 0 时取 dp[j-1]；处理第一个字符时取 0，避免访问不存在的前一项。
根据是否重复，将 prev + 1 或 j - i 写入 dp[j]。
用 res 记录已计算状态的最大值，循环结束后返回。空字符串不进入循环，直接返回 0。

例如 s = "abcabcbb"，最终得到 dp = [1, 2, 3, 3, 3, 3, 2, 1]，最大值是 3。四种语言使用相同的状态定义和转移逻辑：

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        dp = [0] * len(s)
        res = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1)
            dic[s[j]] = j
            prev = dp[j - 1] if j > 0 else 0
            dp[j] = prev + 1 if prev < j - i else j - i
            res = max(res, dp[j])
        return res

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int len = s.length();
        int[] dp = new int[len];
        int res = 0;
        for (int j = 0; j < len; j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);
            dic.put(s.charAt(j), j);
            int prev = j > 0 ? dp[j - 1] : 0;
            dp[j] = prev < j - i ? prev + 1 : j - i;
            res = Math.max(res, dp[j]);
        }
        return res;
    }
}

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> dic;
        int len = s.size();
        vector<int> dp(len, 0);
        int res = 0;
        for (int j = 0; j < len; j++) {
            int i = dic.count(s[j]) ? dic[s[j]] : -1;
            dic[s[j]] = j;
            int prev = j > 0 ? dp[j - 1] : 0;
            dp[j] = prev < j - i ? prev + 1 : j - i;
            res = max(res, dp[j]);
        }
        return res;
    }
};

JavaScript

var lengthOfLongestSubstring = function(s) {
    const dic = new Map();
    const len = s.length;
    const dp = new Array(len).fill(0);
    let res = 0;
    for (let j = 0; j < len; j++) {
        const i = dic.get(s[j]) ?? -1;
        dic.set(s[j], j);
        const prev = j > 0 ? dp[j - 1] : 0;
        dp[j] = prev < j - i ? prev + 1 : j - i;
        res = Math.max(res, dp[j]);
    }
    return res;
};

这个版本的时间复杂度为 O(N)，空间复杂度为 O(N)：除了哈希表，还保留了完整的 dp 数组。接下来观察代码中的 dp[j-1]，就能找到可以压缩空间的原因。

🚀 状态压缩与代码解密

计算本轮 dp[j] 只需要上一轮的 dp[j-1]，最终又只需返回所有状态的最大值，因此不必保留整个 dp 数组，可以用两个变量完成记录：

tmp：手里这一串的长度。 执行本轮转移前，它保存 dp[j-1]；赋值完成后，它保存 dp[j]。它不是始终代表“上一轮”。
res：历史最高纪录。 每算出一个新的 tmp，就用 res = max(res, tmp) 更新，最终返回 res。

下面四种语言都用 tmp 替代完整的 dp 数组，哈希表查询与更新顺序保持一致：

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        tmp = 0
        res = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1)
            dic[s[j]] = j
            tmp = tmp + 1 if tmp < j - i else j - i
            res = max(res, tmp)
        return res

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int tmp = 0;
        int res = 0;
        int len = s.length();
        for (int j = 0; j < len; j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);
            dic.put(s.charAt(j), j);
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = Math.max(res, tmp);
        }
        return res;
    }
}

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> dic;
        int tmp = 0;
        int res = 0;
        int len = s.size();
        for (int j = 0; j < len; j++) {
            int i = dic.count(s[j]) ? dic[s[j]] : -1;
            dic[s[j]] = j;
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = max(res, tmp);
        }
        return res;
    }
};

JavaScript

var lengthOfLongestSubstring = function(s) {
    const dic = new Map();
    let tmp = 0;
    let res = 0;
    const len = s.length;
    for (let j = 0; j < len; j++) {
        const i = dic.get(s[j]) ?? -1;
        dic.set(s[j], j);
        tmp = tmp < j - i ? tmp + 1 : j - i;
        res = Math.max(res, tmp);
    }
    return res;
};

以 Python 为例，每轮循环可以按四个动作阅读：

翻本子：i = dic.get(s[j], -1)，先取出当前口味的旧位置；没见过就得到 -1。
记新位置：dic[s[j]] = j，为后面的水果留下最新记录。一定要先查再写，否则查到的就会是当前位置，而不是旧位置。
调整这一串：tmp = tmp + 1 if tmp < j - i else j - i。赋值右侧的 tmp 还是上一轮长度；不冲突就加 1，冲突就只保留旧水果之后的连续部分。
更新纪录：res = max(res, tmp)，用本轮长度挑战历史最好成绩。当前这一串变短，也不会让历史纪录变小。

例如 abcabcbb 的最后一个位置只能形成长度为 1 的无重复子串，但此前出现过长度为 3 的子串，所以最终返回 3。空字符串不会进入循环，直接返回初始值 0。

📊 复杂度分析

下面分析状态压缩后的版本。设字符串长度为 N，字符集大小为 M。

时间复杂度 O(N)：从头到尾遍历一次，每轮进行一次哈希表查询、一次写入和常数次比较。按哈希表查询与写入平均 O(1) 计算，总时间为 O(N)。
空间复杂度 O(min(N, M))：哈希表最多记录字符串中出现过的不同字符，i、j、tmp、res 只占常数空间。若字符集固定（例如 ASCII），相对于 N 也可记作 O(1)；若不限定字符集，最坏需要 O(N) 空间。

状态压缩省去的是完整 dp 数组的 O(N) 空间，哈希表仍然要保留。

🌟 一句话记住

每拿到一颗新水果，先查它上次出现在哪里：不在前一串里就直接接上，在前一串里就去掉旧水果及其左侧部分，再接上新水果；用 tmp 记这一串的长度，用 res 记历史最长。

动画演示

按顺序选水果、翻小本本、判断是否撞口味，再把新水果串上竹签。遇到串内重复时，移出旧水果及其左侧部分；tmp 记录当前一串的长度，res 保留历史最长纪录。

串出最长的糖葫芦

准备串糖葫芦按顺序选水果，串出连续且口味不重复的一串。

固定水果排 · abcbad准备开始

前一步 0 · 距离 —tmp = —空

▤ 口味小本本 dic

a → —b → —c → —d → —

✦ 最长一串— 颗 · res空

速度步骤 1 / 42