LeetCode 剑指 Offer 48. 最长不含重复字符的子字符串
题目描述
题意分析
在字符串中找一个连续片段，使其中每个字符最多出现一次，返回它的最大长度。题面限定字符为
a到z，可以直接记录每个字母出现的位置。
解法：滑动窗口记录最近位置
核心思路
[!blue]
用
[left, right]表示当前窗口，last[ch]记录字符ch在已扫描前缀中最后一次出现的位置。向右加入新字符前，旧窗口已经没有重复，所以新冲突只可能由当前字符ch引起。设
ch的上次位置为p。若p >= left，旧ch还在窗口中，新的左边界至少要到p + 1才能排除它；若p < left，旧记录已经在窗口外，不会造成重复，左边界保持不变。两种情况合并为left = max(left, p + 1)；从未出现过的字符不需要移动左边界。每次只排除必须舍弃的前缀，保留下来的就是以
right结尾的最长无重复子串。扫描每个右端点并取最大长度，就覆盖了全局答案。last可以保留窗口外的记录，因为比较p与left就能判断它是否仍然有效，无需逐个删除。
解题步骤
- 初始化左边界
left = 0、答案ans = 0和最近位置表last。- 枚举右边界
right，读取新字符ch = s[right]。- 若
ch出现过，用max(left, last[ch] + 1)更新左边界，排除窗口内的旧ch，同时忽略窗口外的旧记录。- 记录
last[ch] = right。此时[left, right]恢复为无重复窗口，用其长度更新ans。- 扫描结束后返回
ans。空字符串不进入循环，返回初始值 $0$。
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (last.containsKey(ch)) {
// 旧出现可能已经离开窗口，左边界只能向右而不能回退。
left = Math.max(left, last.get(ch) + 1);
}
// 先用旧位置修复窗口，再登记当前出现。
last.put(ch, right);
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
func lengthOfLongestSubstring(s string) int {
last := make(map[byte]int)
left := 0
ans := 0
for right := 0; right < len(s); right++ {
ch := s[right]
// 旧出现可能已经离开窗口，只有越过当前左界才需要跳转。
if idx, exists := last[ch]; exists && idx+1 > left {
left = idx + 1
}
// 先用旧位置修复窗口，再登记当前出现。
last[ch] = right
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 为字符串长度。右边界只扫描一次，哈希表查询与更新的均摊时间为 $O(1)$。
- 空间复杂度：$O(1)$。题面只含 $26$ 个小写字母，哈希表每种字母最多保存一条最近位置记录。
关键点总结
[!green]
- 窗口不变量是
[left, right]内字符互不重复。- 最近位置表让左边界一步跳过重复字符，不需要逐个删除窗口元素。
left必须单调不减，max正是为了解决旧记录已经离开窗口的情况。
易错点总结
[!yellow]
- 直接赋值
left = last[ch] + 1，可能被窗口外的旧记录拉回已经排除的位置；应取max。- 最近位置必须先读取再覆盖，否则会把当前位置误认为上一次出现的位置。
- 跳转目标是旧位置的下一格，漏写
+1后重复字符仍在窗口内。- 必须先恢复窗口不变量，再计算
right - left + 1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 159. 至多包含两个不同字符的最长子串 | 中等 | 同样维护可扩张再收缩的字符窗口，原题允许两种字符重复，本题每种字符最多出现一次。 |
| 424. 替换后的最长重复字符 | 中等 | 同样追踪窗口内字符频次，原题允许替换预算，本题遇重复就必须调整左边界。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！