Longest Substring Without Repeating Characters

Problem

Given a string s, find the length of the longest substring (contiguous) without repeating characters.

Examples: "abcabcbb" → 3 ("abc"), "bbbbb" → 1 ("b"), "pwwkew" → 3 ("wke").

What the interviewer is testing

• Do you recognize this as a sliding-window problem within 30 seconds?
• Do you use a set (or hash map) for O(1) duplicate detection?
• When you shrink the window, do you know when to stop?

Why sliding window

The answer is a contiguous range within the string, and we're asked for the "longest with some property". That's the signature of sliding window: expand the right pointer while the property holds, shrink the left pointer when it's violated.

Optimal solution — O(n) time, O(min(n, Σ)) space

Grow the window on the right. If the character at right is already in the set, shrink from left until the offending duplicate is gone, then add and continue.

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Faster: skip directly with a last-seen index

Using a map of char → last index, we can jump left straight past the duplicate instead of shrinking one at a time.

def length_of_longest_substring(s: str) -> int:
    last = {}                         # char -> last index seen
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1        # jump past the duplicate
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Complexity — what to say out loud

"Time O(n) — the right pointer moves n steps, the left pointer only moves forward, so the total work is O(n). Space O(min(n, Σ)) where Σ is the alphabet size — bounded for ASCII."

Edge cases the interviewer will ask about

• Empty string — return 0.
• All identical characters — answer is 1.
• All unique characters — answer is the string length; loop never shrinks.
• Whitespace or symbols — no special handling; a character is a character.

Common follow-ups

• "Longest substring with at most K distinct characters." — Same window skeleton; the shrink condition becomes "distinct count > K".
• "Longest substring with exactly K distinct characters." — At-most(K) − at-most(K−1). Classic decomposition trick.
• "Return the actual substring, not the length." — Track the best (left, right) alongside best; slice at the end.

How to verbalize your answer

"This is sliding window — I want the longest contiguous range with the 'no duplicates' property. I'll expand the right pointer and use a hash set to detect duplicates in O(1). When I find one, I shrink from the left until it's gone. Total work is O(n) because each pointer moves forward at most n times."