Longest Substring Without Repeating Characters

The shape of the window

I want the longest run with no repeats. A run is a window [left, right]. As I push right forward one character at a time, the only thing that can break the window is a character I've already seen inside it. When that happens I shrink from the left until the duplicate is gone, then keep extending.

The answer is the largest right - left + 1 I ever see.

Brute force, then the cut

The naive version checks every substring and tests each for uniqueness: O(n³), or O(n²) if I grow a set per starting index. Both re-scan characters I've already cleared.

The cut is to stop moving left one step at a time. I keep a map from each character to the last index where I saw it. When right lands on a character whose last position is inside the current window, I jump left straight to one past that position. The seen[c] >= left check matters: a stale entry from before the window must not drag left backward.

def length_of_longest_substring(s: str) -> int:
    seen: dict[str, int] = {}
    left = 0
    longest = 0
 
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = right
        longest = max(longest, right - left + 1)
 
    return longest

Why one pass is enough

right advances every iteration and left only ever moves forward, so each index is touched a constant number of times: O(n). The map holds at most one entry per distinct character, so space is O(min(n, k)) for an alphabet of size k. Quick check on "abba": at the second a, its last index is 0 but left is already 2, so the guard keeps left put and I correctly get a length of 2.