medium
Longest Substring Without Repeating Characters
Given a string, find the length of the longest contiguous substring in which no character occurs twice.
Constraints
- 0 ≤ s.length ≤ 5 · 10^4
- s consists of printable ASCII characters
Examples
in: s = "abcabcbb"
out: 3
"abc" is the longest run with distinct characters.
in: s = "bbbbb"
out: 1
Recognition clues
- Asks for a *contiguous* substring
- Validity ("no repeats") is broken by adding characters and restored by removing from the left
- Longest window satisfying a condition
Pattern
Sliding WindowA question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.
Solution
Maintain a window [l, r] and a map from character to its last index. Extend r one step at a time; if s[r] was last seen at an index at least l, jump l to just past that index so the window contains no duplicate. Record r - l + 1 as a candidate after each step. Each pointer moves forward only, so the whole scan is linear.
time O(n)space O(min(n, alphabet))
Alternative approaches
- A brute-force check of every substring with a set is O(n^2) or O(n^3); a frequency-count window that shrinks one step at a time is the same idea as the solution but without the index jump.
Code it yourself
Solve in
Hints: