LeetCode LCR 016. 无重复字符的最长子串
题目描述
题意分析
在字符串
s中寻找不包含重复字符的最长连续子串，返回长度。字符必须占据原串中的一段连续区间，不能跳过中间字符，也不需要返回具体子串内容。题目允许字母、数字、符号和空格，每一种字符都参与判重，不能只处理小写字母或忽略空格。空串没有候选字符，答案为零；其他情况下至少可以选择一个字符。
解法一：滑动窗口 + 最近出现位置
核心思路
[!blue]
用
[left, right]表示当前窗口，并保持窗口内没有重复字符。上一轮窗口已经合法，右端新加入字符ch时，其他字符的次数没有变化，唯一可能新增的冲突就是ch与窗口中以前出现的同一字符。用
lastIndex保存每个字符在整个已扫描部分中最近出现的下标。若旧位置preIndex >= left，它仍在当前窗口内；要同时保留新的右端，左端至少必须移到preIndex + 1，否则这两个相同字符都会留在窗口中。跳到这里恰好移除了旧副本，其他字符原本互不相同，所以窗口马上恢复合法，无需继续收缩。若旧位置在
left之前，它属于已经移出的历史，不构成当前重复。此时不能把左端改回旧位置之后，否则左端会回退，并可能重新纳入之前排除的重复字符。只在旧位置仍有效时前移，保证左端单调向右。修复后再把当前下标写入映射，并更新长度
right - left + 1。左端始终停在能保留当前右端的最早合法位置，所以本轮窗口是以当前右端结尾的最长无重复子串；枚举全部右端并取最大值，即得到全局答案。
解题步骤
- 初始化空的最近位置表、左端
left = 0和答案零。- 从左到右枚举
right，先读取当前字符的旧最近位置。- 旧位置存在且不小于
left时，将左端移到旧位置的下一位；否则保持不变。- 记录当前字符最近出现在
right。- 用已经合法的窗口长度更新答案，扫描结束返回最大值。
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastIndex = new HashMap<>();
int left = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
Integer preIndex = lastIndex.get(ch);
if (preIndex != null && preIndex >= left) {
// left 只越过当前窗口内的重复字符，保证窗口边界单调右移。
left = preIndex + 1;
}
lastIndex.put(ch, right);
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
func lengthOfLongestSubstring(s string) int {
lastIndex := make(map[byte]int)
left := 0
ans := 0
for right := 0; right < len(s); right++ {
ch := s[right]
if preIndex, ok := lastIndex[ch]; ok && preIndex >= left {
// left 只越过当前窗口内的重复字符，保证窗口边界单调右移。
left = preIndex + 1
}
lastIndex[ch] = right
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}
复杂度分析
- 时间复杂度：期望
O(n)。每个右端只做常数次哈希操作，左端只向右跳转。- 空间复杂度：
O(min(n, C))，其中C是字符集大小，映射保存扫描中出现过的各字符最近位置。
关键点总结
[!green]
- 最近位置表保存全局历史，左端决定历史位置是否仍属于当前窗口。
- 新加入的字符是本轮唯一可能产生重复的字符，直接越过其旧位置即可。
- 先读取旧位置，再更新映射；先恢复合法，再记录答案。
解法二：滑动窗口 + 字符计数
核心思路
[!blue]
另一种表示方式是保存当前窗口中各字符的频次
count。新右端字符ch入窗后计数加一，若它出现超过一次，就从左边逐个移出字符，同步减少被移出字符的计数。只需检查
count[ch] > 1：进入本轮之前所有字符都不重复，本轮仅增加了ch。移出其他字符虽然未立即解决这次重复，但能继续靠近旧的ch；一旦旧副本被移出，计数回到一，其他字符也不会因为移出而产生新重复，窗口就恢复合法。收缩停在刚好合法的位置，与最近位置写法越过旧副本后的边界相同，因此同样得到当前右端对应的最长合法窗口。每次加入一个字符最多把右端推进一步，每次移出把左端推进一步，内层循环累计不会超过字符串长度。
映射里的计数描述当前窗口，但代码不会删除已经归零的键。保留这些键不会影响正确性，只是计算空间时应按扫描中见过的字符种类，而不是当前非零种类计算。
解题步骤
- 初始化空计数表，令左端和答案都为零。
- 加入当前右端字符，将其窗口频次加一。
- 当新增字符的频次大于一时，减少
s[left]的计数并让左端右移。- 新增字符不再重复后，用当前窗口长度更新答案。
- 全部右端扫描完后返回最大值。
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> count = new HashMap<>();
int left = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
count.put(ch, count.getOrDefault(ch, 0) + 1);
while (count.get(ch) > 1) {
// 只收缩到本轮新增字符不重复，窗口就恢复合法。
char removed = s.charAt(left);
count.put(removed, count.get(removed) - 1);
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
func lengthOfLongestSubstring(s string) int {
count := make(map[byte]int)
left := 0
ans := 0
for right := 0; right < len(s); right++ {
ch := s[right]
count[ch]++
for count[ch] > 1 {
// 只收缩到本轮新增字符不重复，窗口就恢复合法。
removed := s[left]
count[removed]--
left++
}
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}
复杂度分析
- 时间复杂度：期望
O(n)。每个位置至多加入窗口一次、移出一次，所有收缩次数的总和为线性。- 空间复杂度：
O(min(n, C))。代码保留计数归零的键，映射最多保存整个扫描过程中出现过的字符种类。
关键点总结
[!green]
- 窗口原本合法，所以每轮只检查新增字符的频次是否超出一。
- 左端移动与计数减少必须同步，使状态始终对应实际窗口。
- 收缩循环累计次数由左端总移动量决定，不能直接按嵌套层数判成平方复杂度。
解法对比：
最近位置写法保存历史下标，直接跳过窗口内的重复位置；计数写法保存当前窗口频次，逐个移出左端直到恢复合法。两者都保留以每个右端结尾的最长无重复窗口，时间同为线性，区别在于怎样表示并消除重复。
易错点总结
[!yellow]
- 旧位置已在窗口之外仍修改左端：会造成边界回退，重新带入已经排除的重复。
- 先写最近位置再读取旧位置：读到的是当前下标自己，无法判断真正的历史冲突。
- 恢复合法之前更新答案：会把含重复字符的窗口计入结果。
- 计数写法只移动左端、不减少频次：状态与窗口不一致，无法正确结束收缩。
- 把答案初值设为一：空串需要返回零。
- 忽略空格、符号或字符连续性：它们都属于原串内容，必须按题目要求逐位置参与判定。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 159. 至多包含两个不同字符的最长子串 | 中等 | 同样维护可扩张再收缩的字符窗口，原题允许两种字符重复，本题每种字符最多出现一次。 |
| 424. 替换后的最长重复字符 | 中等 | 同样追踪窗口内字符频次，原题允许替换预算，本题遇重复就必须调整左边界。 |