Longest Substring Without Repeating Characters

We need to find the length of the longest substring in a given string s that contains no duplicate characters.

A substring is a contiguous sequence of characters. For example, in "abcabcbb", "abc" is a substring, but "acb" is not (it skips characters).

We use the Sliding Window technique with a Hash Map (or Array for fixed charsets) to track characters in the current window.

1. Initialize left = 0 and max_len = 0.
2. Use a map to store the most recent index of each character.
3. Iterate right from 0 to end of string:
   • If s[right] is in map and its index is >= left, it means we found a repeat inside our current window. Move left to map[s[right]] + 1 to skip the previous occurrence.
   • Update map[s[right]] to the current right index.
   • Update max_len = max(max_len, right - left + 1).
4. Return max_len.

Key Insight: Instead of shrinking the window one character at a time, we can jump the left pointer directly past the duplicate. Both versions are O(N); the jump just skips the inner shrinking loop.

Watch how the window expands and jumps the left pointer when a duplicate is found.