Longest Substring

def longest_substring(s):
    last = {}              # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Longest Substring Without Repeating Characters. Given a string, find the length of the longest run of characters with no repeats.

Take B, C, D, C, E, F, B. The answer is five: D, C, E, F, B, all different.

The naive way checks every substring for repeats. There are about n squared substrings, and checking each takes up to n steps, so that's n cubed. Even with a set, it's n squared.

Instead, slide a window. The right edge takes one new character at a time, and a map remembers where each character was last seen. If the new one was last seen inside the window, the left edge jumps just past that copy. Each window length is a candidate for the best.

In code, for each character, if its last index is at least left, move left to that index plus one. Then store the new index and update the best.

Let's ride it. B, C and D board: length three. Then C arrives, last seen at one, inside the window. Left jumps from zero to two, past two cars at once. E and F board: length four, a new best. Now B arrives. It was seen at zero, but that's behind the left edge, so nothing moves. Length five, the best.

Each character boards once and the left edge never moves back, so the time is order n. The map holds one entry per distinct character.

Stretch right, jump left, never look back. That's Longest Substring.