Longest Substring Without Repeating Characters
Grow a window; when a repeat appears, shrink from the left past it.
Approach
Maintain a window and a map of each character's last index. Expand the right edge; if the incoming character was seen inside the current window, jump the left edge just past its previous position. The longest window width seen is the answer.
Time complexity
O(n)
Space complexity
O(min(n, alphabet))
Common mistake
Moving the left pointer to lastIndex instead of lastIndex + 1, or not ignoring stale indices outside the window.
See it run, step by step
Generate an interactive lesson for Longest Substring Without Repeating Characters — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Longest Substring Without Repeating Characters