Longest Substring Without Repeating Characters

1. The obvious way

   Check every substring for duplicates: O(n³), or O(n²) with a set.

2. The key insight

   Keep a window with no repeats. When the new character was last seen inside the window, move the left edge to just after that earlier spot, in one jump, no removals one by one. Note the window width at every step.

3. The algorithm
   1. Notebook: last position of every character. Left edge at the start. Best = 0.
   2. Take the next character at the right edge.
   3. Was it last seen inside the window? Move the left edge to just after that spot.
   4. Write down its new position; best = max(best, window width).

Watch it run

best 3

def length_of_longest_substring(text):
    last_seen = {}                                  # character -> last position
    left = 0                                        # left edge of the window
    best = 0
    for right, character in enumerate(text):
        if last_seen.get(character, -1) >= left:    # repeat inside the window
            left = last_seen[character] + 1         # jump past the earlier one
        last_seen[character] = right
        best = max(best, right - left + 1)
    return best

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.