跳到主要内容

1 / 4思路

Longest Substring Without Repeating Characters

原题

思路​

维护一个无重复字符的窗口 [left, right]。右端每次纳入一个新字符;如果它上次出现的位置仍在窗口内,就把 left 移到上次位置之后。窗口长度取最大值。

复杂度​

  • 时间 O(n):每个字符进窗口一次、出窗口一次。
  • 空间 O(Σ):字符集大小,ASCII 时可视为 O(1)。

代码​

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

边界​

  • 空串:返回 0。
  • 全部字符相同:窗口长度始终为 1。
  • 字符集含 Unicode:用 Map/字典按字符而非字节计数。