Longest Substring Without Repeating Characters, Done Right

If you interview at Amazon, Google, Meta, expect some version of "Longest Substring Without Repeating Characters". It is rated Medium, and it falls squarely into the Sliding Window pattern — pattern-first preparation beats grinding random problems every time. Part 2 of 11 in the Sliding Window arc.

The Problem

Given a string s, find the length of the longest substring without repeating characters. By most published company lists this is among the most frequently asked coding questions anywhere, so the bar for a clean solution is high.

Input:  s = "abcabcbb"
Output: 3
The answer is "abc". Note "abca" fails because "a" repeats.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Longest substring under a constraint — all characters distinct — is the variable-size window signature. Grow the right edge; when the constraint breaks, move the left edge just far enough to restore it. Never restart from scratch.

The Approach

Keep last_seen, mapping each character to its most recent index. When s[right] was seen inside the current window, jump left directly past that previous occurrence — no incremental shrinking loop needed. Update the answer on every step.

The jump version is worth the extra thought over the shrink-one-at-a-time version: same O(n), but it shows you understand why the left edge moves, not just that it does.

Python Solution

def length_of_longest_substring(s: str) -> int:
    """Length of the longest substring with all distinct characters."""
    last_seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the previous occurrence
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Complexity

• Time: O(n) — right scans once; left only jumps forward
• Space: O(min(n, alphabet)) — the last-seen map holds at most one entry per distinct character

Interview Tips and Follow-Ups

• Test yourself on "abba": without the last_seen[ch] >= left guard, left moves backwards and the answer is wrong. This is the bug interviewers wait for.
• Escalations: at most two distinct characters, or at most k distinct — both later in this arc's family, same skeleton with a counts map.
• If the alphabet is fixed (ASCII), state that the map is O(1) space — precision on space complexity reads as seniority.

More Sliding Window problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.