The problem
Given a string s, return the length of the longest substring — a stretch of consecutive characters — in which no character appears twice.
Examples
01
- Input
s = "abcabcbb"
- Output
3
02
- Input
s = "bbbbb"
- Output
1
03
- Input
s = "pwwkew"
- Output
3
Constraints
- 0 ≤ s.length ≤ 5 × 10⁴
sconsists of English letters, digits, symbols and spaces.
The idea
Grow a window [l, r] one character at a time. It stays valid as long as the new character is not already inside it.
Remember where each character was last seen. When s[r] was last seen at or after l, the window now holds it twice, so jump l to just past that earlier copy. After each step the window is the longest valid one ending at r; the best of those is the answer.
- Time
- O(n) — each character enters the window once
- Space
- O(1) — at most 128 remembered positions
Solution · every language run against every case
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last = {} # character -> index where it was last seen best = l = 0 for r, c in enumerate(s): if c in last and last[c] >= l: l = last[c] + 1 # jump the window's start past the earlier copy last[c] = r best = max(best, r - l + 1) return best