You are given a string s. Return the length of the longest substring (a contiguous run of
characters) in which no character appears more than once.
Example 1
- Input
- s = "abcbdea"
- Output
- 5
cbdea has five different characters. Stretching it left would bring in a second b.Example 2
- Input
- s = "zzzz"
- Output
- 1
Example 3
- Input
- s = "ab ba"
- Output
- 3
ab and ba both work.Constraints
sholds 0 to 5 × 10⁴ characters.- Every character is printable ASCII: letters, digits, symbols and spaces.
Show the pattern
Sliding window
You want the longest contiguous stretch that obeys a rule (no character twice). Grow a window on the right, and when a repeat comes in, move the left edge past the earlier copy.
See sliding window in a visualiserShow the approach
Slide a window [left, right] along the string, keeping it free of repeats. Keep a hash map from
each character to the last index where it appeared. For each right, if s[right] was last seen
at an index ≥ left, that copy is inside the window: move left to one past it. Then record
right as the character's last index, and update the best length with right − left + 1.
left never moves backwards (that's what the ≥ left check ensures, as in abba), so every
character joins and leaves the window once.
Time: O(n) · Space: O(k) for k different characters