Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring with all distinct characters. The brute force enumerates every start index and extends until a duplicate — O(n²). The machine can do it in one pass with a sliding window.

The key insight: maintain a window [left, right) that is always duplicate-free, growing it rightward. When a character repeats, the window is invalid — but instead of restarting at left + 1, the machine can jump left past the previous occurrence of that character, because every shorter window between is provably no better than what was already measured.

Approach:

1. Walk right across the string; record each character's latest index.
2. On a repeat, move left to one past the stored index (or keep it, whichever is further right).
3. Update the best length after each step.

def length_of_longest_substring(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

Time: O(n). Space: O(min(n, alphabet size)).

Trickiest edge case: the stale-index guard seen[ch] >= left — a character seen before the window's left edge must not shrink the window, or "abba" produces the wrong answer.