无重复字符的最长子串

题目描述

在字符串 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 (结果)：记录毛毛虫历史上最长的身体长度。

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

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

动画演示

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

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

状态定义与转移方程

动画演示