Longest Substring Without Repeating Characters

Interview Prep

StandardSliding Windowstringssliding-window

The problem

Given a string s, return the length of the longest substring with all distinct characters. Substring means contiguous; "subsequence" is a different problem.

Pattern: sliding window with a "last seen" map

A sliding window is a pair of pointers — left and right — that defines a contiguous range. The right pointer expands, the left pointer contracts when a constraint breaks. For "longest substring with property P," the window grows while P holds and shrinks the moment P fails.

Recognize this pattern when the question says "longest" or "shortest" plus "contiguous" plus a per-window property. Two pointers, one pass, no nested loops.

Brute force

def length_of_longest_substring(s: str) -> int:
    best = 0
    for i in range(len(s)):
        seen = set()
        j = i
        while j < len(s) and s[j] not in seen:
            seen.add(s[j])
            j += 1
        best = max(best, j - i)
    return best

O(n²) time, O(min(n, alphabet)) space. For each start index, walk forward until a repeat. Correct, but does the same work many times.

Optimal — sliding window

def length_of_longest_substring(s: str) -> int:
    last: dict[str, int] = {}      # char -> most recent index
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best

O(n) time, O(min(n, alphabet)) space. The right pointer marches once. The left pointer jumps directly to one past the previous occurrence whenever a repeat hits. Each character is visited at most twice — once by right, once by left — so it's strictly linear.

The last[c] >= left check is the subtle bit. The map remembers every character ever seen, including ones that have already left the window. We must verify the previous occurrence is still inside the current window before jumping the left pointer.

Walkthrough

s = "abcabcbb"

right=0 c='a' last={}                left=0  →  window "a"      best=1
right=1 c='b' last={a:0}             left=0  →  window "ab"     best=2
right=2 c='c' last={a:0,b:1}         left=0  →  window "abc"    best=3
right=3 c='a' last={a:0,b:1,c:2}     left=1  →  window "bca"    best=3
right=4 c='b' last={a:3,b:1,c:2}     left=2  →  window "cab"    best=3
right=5 c='c' last={a:3,b:4,c:2}     left=3  →  window "abc"    best=3
right=6 c='b' last={a:3,b:4,c:5}     left=5  →  window "cb"     best=3
right=7 c='b' last={a:3,b:6,c:5}     left=7  →  window "b"      best=3

Edge cases

Related