Longest Substring Without Repeating

Signal

"Longest substring with a uniqueness constraint" is the sliding-window signature: a variable-size window over a string where a violation (a repeat) can only be fixed by shrinking from the left.

Approach

Expand the right edge one character at a time. Keep a map from character to the last index it was seen at. If the incoming character was already seen at or after the current left edge, jump left forward to just past that prior occurrence. Track the widest window seen after each expansion.

Skeleton

last_seen = {}
left = 0
best = 0
for right, c in enumerate(s):
    if c in last_seen and last_seen[c] >= left:
        left = last_seen[c] + 1
    last_seen[c] = right
    best = max(best, right - left + 1)

Solution

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

Complexity

O(n) time — left only ever moves forward, so every index enters and exits the window at most once. O(min(n, alphabet size)) space for the index map.

Pitfalls

• Shrinking left one step at a time in a while loop instead of jumping straight to last_seen[c] + 1 — still correct, but easy to get the shrink condition wrong, since a plain set tells you that there's a duplicate but not where, which is why the index map matters.
• Forgetting the last_seen[c] >= left guard — without it, a stale index from before the current window can yank left backward incorrectly.
• Off-by-one on window length: it's right - left + 1, not right - left.