3. 无重复字符的最长子串
题目描述
输入一个字符串 s。子串指 s 中一段连续的字符。
在所有内部没有重复字符的子串里，找出最长的一个，返回它的长度。s 为空时返回 0。
示例 1
输入：s = "abcabcbb" 输出：3
解释："abc" 没有重复字符，长度为 3；再长就一定出现重复。
示例 2
输入：s = "bbbbb" 输出：1
解释：每个子串只要长度超过 1 就会重复，最长的是 "b"。
示例 3
输入：s = "pwwkew" 输出：3
解释：最长的是 "wke"，长度 3。"pwke" 不连续，是子序列而不是子串。
数据范围
0 <= s.length <= 10^5s中可能出现英文字母、数字、符号和空格。
解题思路：滑动窗口（记录下标跳跃）
右指针扩展窗口，记录字符最近出现位置；若重复字符落在窗口内，就把左边界跳到其后一位。
为什么正确
窗口 s[left:right+1] 始终没有重复字符，best 是已处理窗口的最大长度。
复杂度分析
时间 O(n)，空间 O(min(n,字符集大小))。
易错点
重复字符在窗口外时不能把 left 向后跳错；要判断 last[ch] >= left。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lengthOfLongestSubstring(self, s):
last={}; left=0; best=0
for right,ch in enumerate(s):
if ch in last and last[ch] >= left: left=last[ch]+1
last[ch]=right
best=max(best,right-left+1)
return bestclass Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>(); int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (last.containsKey(ch) && last.get(ch) >= left) left = last.get(ch) + 1;
last.put(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}
}class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> last; int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
char ch = s[right];
if (last.count(ch) && last[ch] >= left) left = last[ch] + 1;
last[ch] = right;
best = max(best, right - left + 1);
}
return best;
}
};func lengthOfLongestSubstring(s string) int {
last := map[byte]int{}; left, best := 0, 0
for right := 0; right < len(s); right++ {
ch := s[right]
if j, ok := last[ch]; ok && j >= left {
left = j + 1
}
last[ch] = right
best = max(best, right-left+1)
}
return best
}var lengthOfLongestSubstring = function(s) {
const last = new Map(); let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
if (last.has(ch) && last.get(ch) >= left) left = last.get(ch) + 1;
last.set(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
};function lengthOfLongestSubstring(s: string): number {
const last = new Map<string, number>(); let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
if (last.has(ch) && last.get(ch)! >= left) left = last.get(ch)! + 1;
last.set(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
};其他解法
两种做法都维护无重复字符的窗口；集合版逐步收缩左边界，下标表版直接跳跃左边界。
解法 2：滑动窗口 + 哈希集合 时间 O(n)，空间 O(min(n,Σ))
用哈希集合保存窗口内的字符。右指针每读入一个字符，若它已在集合中，就不断移除 s[left] 并右移 left，直到重复字符离开窗口。然后把新字符加入集合，并用窗口长度更新答案。Σ 为字符集大小。
左边界一步一步收缩，每个字符最多进出集合各一次，仍是 O(n)。主解法记录最近下标，可以让左边界一次跳到位，常数更小；集合版的窗口收缩过程更直观。
class Solution:
def lengthOfLongestSubstring(self, s):
window = set()
left = best = 0
for right, ch in enumerate(s):
while ch in window:
window.remove(s[left])
left += 1
window.add(ch)
best = max(best, right - left + 1)
return bestclass Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
while (window.contains(ch)) {
window.remove(s.charAt(left));
left++;
}
window.add(ch);
best = Math.max(best, right - left + 1);
}
return best;
}
}class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> window;
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
while (window.count(s[right])) {
window.erase(s[left]);
left++;
}
window.insert(s[right]);
best = max(best, right - left + 1);
}
return best;
}
};func lengthOfLongestSubstring(s string) int {
window := map[byte]bool{}
left, best := 0, 0
for right := 0; right < len(s); right++ {
for window[s[right]] {
delete(window, s[left])
left++
}
window[s[right]] = true
if right-left+1 > best {
best = right - left + 1
}
}
return best
}var lengthOfLongestSubstring = function(s) {
const window = new Set();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
while (window.has(s[right])) {
window.delete(s[left]);
left++;
}
window.add(s[right]);
best = Math.max(best, right - left + 1);
}
return best;
};function lengthOfLongestSubstring(s: string): number {
const window = new Set<string>();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
while (window.has(s[right])) {
window.delete(s[left]);
left++;
}
window.add(s[right]);
best = Math.max(best, right - left + 1);
}
return best;
};