Find the length of the longest substring without repeating characters.
Use a variable-size sliding window with a hash map that records the most recent index of each character. When the right pointer hits a character already in the window, jump the left pointer to one past that character's last position — skipping over the repeat in one move rather than crawling one step at a time.
How to think about it
Recognise the pattern
The signal is “longest/shortest window satisfying a constraint” on a string or array. When the window size is variable (you grow it until it violates a rule, then shrink it), you’re in variable sliding-window territory. The constraint here is “no repeating character inside the window.” The hash map stores where each character was last seen so you can jump left instantly instead of crawling.
Build the approach step by step
Brute force checks every substring by generating all O(n²) pairs (i, j) and scanning each for uniqueness. O(n³) time, or O(n²) with a set.
The insight: keep a window [left, right] that always contains unique characters. Expand right one character at a time. When s[right] is already in the window (i.e. it was seen at some index >= left), the duplicate is at seen[s[right]]. You can teleport left to seen[s[right]] + 1 — the window is now duplicate-free again, and you didn’t re-scan anything.
Walk through "abcabcbb":
- a(0), b(1), c(2): window [0,2], len=3
- a(3): seen at 0, left jumps to 1. Window [1,3], len=3
- b(4): seen at 1, left jumps to 2. Window [2,4], len=3
- c(5): seen at 2, left jumps to 3. Window [3,5], len=3
- b(6): seen at 4, left jumps to 5. Window [5,6], len=2
- b(7): seen at 6, left jumps to 7. Window [7,7], len=1
- Best = 3 ✓
Complexity
- Time — O(n):
rightvisits each character once;leftonly moves forward, so it also visits each character at most once. - Space — O(min(n, alphabet)): the hash map holds at most one entry per distinct character. For ASCII that’s at most 128 entries, effectively O(1).