1 / 4思路
Longest Substring Without Repeating Characters
思路
维护一个无重复字符的窗口 [left, right]。右端每次纳入一个新字符;如果它上次出现的位置仍在窗口内,就把 left 移到上次位置之后。窗口长度取最大值。
复杂度
- 时间 O(n):每个字符进窗口一次、出窗口一次。
- 空间 O(Σ):字符集大小,ASCII 时可视为 O(1)。
代码
- Python
- TypeScript
def length_of_longest_substring(s: str) -> int:
last: dict[str, int] = {}
left = best = 0
for right, char in enumerate(s):
if char in last and last[char] >= left:
left = last[char] + 1
last[char] = right
best = max(best, right - left + 1)
return best
function lengthOfLongestSubstring(s: string): number {
const last = new Map<string, number>();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right += 1) {
const ch = s[right];
const previous = last.get(ch);
if (previous !== undefined && previous >= left) left = previous + 1;
last.set(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}
边界
- 空串:返回 0。
- 全部字符相同:窗口长度始终为 1。
- 字符集含 Unicode:用 Map/字典按字符而非字节计数。