Longest Substring Without Repeating Characters

How you get there

1. 1Extend the window rightwards one character at a time.
2. 2On a repeat, jump the left edge to just past the previous occurrence.
3. 3The left edge must never move backwards, which is what keeps it O(n).

Solution

def length_of_longest_substring(s: str) -> int:
    last: dict[str, int] = {}
    start = best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1        # guard stops the left edge going backwards
        last[ch] = i
        best = max(best, i - start + 1)
    return best

Time

O(n)

Space

O(min(n, alphabet))

What goes wrong

Dropping the `last[ch] >= start` check lets a stale occurrence drag the window left again.