visual walkthrough
Longest Substring Without Repeating Characters
The canonical variable window; one of the most-asked questions anywhere.
The idea
The answer is the longest stretch with no repeated letter. Instead of restarting for every start position, keep one window and slide it: extend on the right, and when the new letter is already inside, drop letters from the left until it isn't.
Each letter enters and leaves the window at most once, so the whole scan is linear.
Complexity
| approach | time | space |
|---|---|---|
| Try every start | O(n²) | O(n) |
| Sliding window | O(n) | O(n) |