Longest Substring Without Repeating Characters (LeetCode 3)

The problem

You get a string s. Return the length of the longest substring (contiguous characters) in which no character appears twice.

Input:  s = "abcabcbb"
Output: 3

"abc" has three distinct characters. Every longer substring contains a repeat.

How to think about it

Start with brute force. Check every substring and test whether its characters are unique. There are O(n²) substrings and each check costs up to O(n), so O(n³). Even with a set that grows as you extend each start point, it’s still O(n²).

Notice what a repeat tells you. Suppose the window s[start..i-1] has no repeats and s[i] is a character already inside it, at position p. Any window that starts at or before p and reaches i contains two copies. So no valid window ending at i can start before p + 1. You can jump start straight there.

The key insight: remember where each character was last seen. Keep a map seen[c] of the last index of each character. When s[i] was seen at an index inside the current window (seen[c] >= start), set start = seen[c] + 1. Otherwise the window simply grows. Each step is O(1), and start only ever moves right.

Why the >= start check matters. The map remembers old positions too. If c was last seen before the window began, it’s not actually in the window, and jumping back to it would move start left, which is wrong.

Which pattern is this? A variable-size sliding window. The tell is “longest substring such that …” with a condition you can repair by moving the left edge.

Approach

1. Keep seen (char → last index), start = 0, best = 0.
2. For each index i and character c: if c is in seen and seen[c] >= start, set start = seen[c] + 1.
3. Record seen[c] = i.
4. Update best = max(best, i - start + 1).
5. Return best.

Solution

def length_of_longest_substring(s):
    seen = {}; start = 0; best = 0
    for i, c in enumerate(s):
        if c in seen and seen[c] >= start: start = seen[c] + 1   # jump past the repeat
        seen[c] = i; best = max(best, i - start + 1)
    return best
# length_of_longest_substring("abcabcbb") -> 3

Dry run

On s = "abcabcbb":

(At i = 1 the window is ab and best is 2.) The answer is 3.

Complexity

• Time: O(n). One pass; each step is a dictionary lookup and update.
• Space: O(min(n, charset)). The map holds at most one entry per distinct character.

Edge cases and pitfalls

• Empty string returns 0.
• All the same character ("bbbb") returns 1; start moves to i each time.
• Forgetting seen[c] >= start breaks inputs like "abba": at the final a, the old index 0 is outside the window, and jumping to 1 would move start backwards and give 3 instead of 2.
• Shrinking one step at a time with a set also works in O(n), but the jump is cleaner.
• Substring, not subsequence. The characters must be contiguous.

Related problems

• Longest Repeating Character Replacement (LeetCode 424): a variable window with a “replacements budget” instead of “no repeats”.
• Fruit Into Baskets (LeetCode 904): the longest window with at most two distinct values.
• Minimum Window Substring (LeetCode 76): the “shortest valid window” version of the same template.