Problem 9 · Two Pointers & Sliding Window

Longest Substring Without Repeating Characters

MediumClassic DSA & systems

01Problem

Return the length of the longest substring of s with no repeated characters.

02Key insight

Variable-size sliding window with a last-seen index map: on a repeat, jump the left edge past the previous occurrence instead of shrinking one step at a time.

03Solution

solution.pypython9 lines

def length_of_longest_substring(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = best = 0
    for right, ch in enumerate(s):
        if last_seen.get(ch, -1) >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Try it first.

TimeO(n)

SpaceO(min(n, alphabet))

tests.py · 4 passing

tests.pypython4 lines

assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("") == 0
assert length_of_longest_substring("abba") == 2

04Staff-level follow-up

Allow at most k distinct characters instead? Keep a count map and shrink from the left while len(map) > k; same O(n) window.