跳到正文
第 3 题中等

无重复字符的最长子串

Longest Substring Without Repeating Characters

在字符串中找一段连续、没有重复字符的子串，返回它的最大长度。

在力扣中练习

题目描述

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

 

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

 

提示：

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

解题思路

主解法

滑动窗口 · 最近出现位置

右端扩张遇到重复，左端只向前跳

暴力枚举每段子串会重复检查很多字符。换个角度：固定右端点，维护以它结尾的最长无重复窗口。

用自拟输入 abcbadefbg 推演。维护 last[ch] 记录字符上次出现的位置，[left, right] 表示当前窗口。读到下标 3 的 b 时，上次位置 1 仍在窗口里，必须让 left 跳到 2，越过旧 b。

分步图解

读到 "b"，上次位置为 1。

left
0
right
3
previous
1
best
3
连续窗口 [left, right]
0
1
2
3
4
5
6
7
8
9
a
b
c
b
a
d
e
f
b
g
left
right
当前字符与下标 1 冲突，需要先恢复窗口合法性。
last：字符最近一次出现的位置
a→0
b→1
c→2
历史记录可以在窗口之外；只有 previous ≥ left 才构成当前窗口中的重复。
1 / 5
读到下标 3 的 b，先跳过旧 b，再继续扩张。

关键是出现过不等于当前窗口内重复。读到下标 4 的 a 时，上次位置为 0，已经小于 left = 2，直接忽略；如果无条件写 left = last[ch] + 1，左边界就会倒退，把重复字符重新放进窗口。

分步图解

读到 "a"，上次位置为 0。

left
2
right
4
previous
0
best
3
连续窗口 [left, right]
0
1
2
3
4
5
6
7
8
9
a
b
c
b
a
d
e
f
b
g
left
right
窗口内无重复；灰色字符已离开窗口。
last：字符最近一次出现的位置
a→0
b→3
c→2
历史记录可以在窗口之外；只有 previous ≥ left 才构成当前窗口中的重复。
1 / 4
下标 4 的 a 以前出现过，但旧位置已在窗口之外，left 保持 2。

继续向后，窗口先扩张出 cbadef，长度为 6；下标 8 的 b 再次触发收缩。每轮恢复合法后再更新 best，最终答案为 6。左右边界都只向右走，所以整体时间为 O(n)。

时间 O(n)空间 O(1)（固定字符表）

易错点

  • left 只能向右移动；窗口外的历史位置不能让它倒退。
  • 先查询旧 last，再登记当前下标，避免与自己产生冲突。
  • 题目要求连续子串，不能把不相邻的字符拼在一起。

代码与演示

演示输入s = "abcbadefbg"

窗口初始为空，所有字符的上次出现位置视为 -1。

left
0
right
-1
previous
-1
best
0
连续窗口 [left, right]
0
1
2
3
4
5
6
7
8
9
a
b
c
b
a
d
e
f
b
g
窗口内无重复；灰色字符已离开窗口。
last：字符最近一次出现的位置
{ }
历史记录可以在窗口之外；只有 previous ≥ left 才构成当前窗口中的重复。
1 / 11
查看 C++ 代码

延伸阅读

  • 滑动窗口的顺序是扩张、恢复约束、更新答案。
  • 这里用固定 256 大小的字符表，并将 char 转成 unsigned char 后作为索引。