Longest Substring Without Repeating Characters

Longest substring without repeating characters finds the longest substring in which no character appears twice. The brute force checks every substring for duplicates at O(n³), and a sliding window reduces that to a single pass. The window holds a stretch of characters that are all distinct. Extending the right edge is always allowed unless the incoming character is already inside the window — and that is the whole condition: - When a repeat appears, the window must shrink from the left until the earlier copy of that character is excluded. The naive shrink advances the left pointer one step at a time. That is correct, and still linear overall since the left pointer never moves backwards. The optimised version jumps instead of stepping. Storing each character's last index in a map lets the left pointer move directly past the previous occurrence in one operation. That jump has a trap. The left pointer must move to max(left, lastIndex + 1), never backwards: In a string like "abba", when the second a is reached, its stored index is 0 — well behind the current left pointer. Jumping there unconditionally reopens a window containing a duplicate b, and the answer comes out too large. Taking the maximum prevents it. The length must be measured after the window is made valid, not before. Space is O(min(n, charset)), since the map holds at most one entry per distinct character rather than one per position.

Two clues put you on a sliding window: the answer is a contiguous stretch, and the constraint is monotone — once a window is invalid, growing it right can't fix it. Then ask whether the left edge should crawl or jump. If you can store where the offender was, jump the left edge past it in O(1) instead of shrinking one character at a time.