Longest Substring Without Repeating Characters

Hints

1. State the invariant first. "The window s[left..right] contains no repeated character." Every line you write either preserves that or restores it. Without naming it you will write the right code and be unable to defend it.
2. Grow on the right, repair on the left. Advance right one character at a time. If the new character breaks uniqueness, move left forward until it holds again. Record the best length after every repair, because the window is valid at that moment.
3. Notice why this is still linear. left and right each only ever move forward, so together they traverse at most 2n positions regardless of how much the window expands and contracts. The nested loop is a mirage; it does not multiply the work.
4. Upgrade from a set to a map of last-seen indices. A set answers "is this character in the window?" and forces you to walk left forward one removal at a time. A map from character to its most recent index answers "where was it?", letting left jump to last_seen[ch] + 1 in a single step.
5. Guard against stale entries. The map holds the globally most recent index, which may be behind left and therefore outside the window. Only jump when last_seen[ch] >= left. On "abba", without this guard the final a drags left backwards to index 1 and the window becomes incoherent.
6. Size the memory by the alphabet, not the string. The map holds at most one entry per distinct character, so space is O(min(m, n)) where m is the alphabet size. For ASCII that is a 128-slot array and a constant.

Solution: three approaches

Approach 1 - Check every substring: O(n^3) time, O(min(m, n)) space

The definition, transcribed directly.

def longest_unique_brute(s):
    n, best = len(s), 0
    for i in range(n):
        for j in range(i, n):
            window = s[i:j + 1]
            if len(set(window)) == len(window):
                best = max(best, j - i + 1)
    return best

There are n(n+1)/2 substrings and testing each for uniqueness costs O(n), so the total is Theta(n^3). At n = 5 * 10^4 this is astronomically out of reach. It is still worth writing on the whiteboard for thirty seconds, because it defines correctness precisely and gives you a reference implementation to test the fast version against. It also makes the wasted work visible, which is what motivates the fix: the substring starting at i and the one starting at i + 1 overlap almost entirely, yet this version rebuilds the uniqueness test from scratch for each. Any time two adjacent subproblems share nearly all of their input, there is a sliding-window solution waiting, and naming that observation is a better route to the optimal algorithm than recognising the problem by its title. Generate random strings over a three-letter alphabet and diff this against your fast version; three letters make collisions frequent enough that bugs surface within a few dozen cases.

Approach 2 - Sliding window with a set: O(n) time, O(min(m, n)) space

The first real algorithm: grow right, shrink left one character at a time.

def longest_unique_set(s):
    window = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in window:
            window.remove(s[left])
            left += 1
        window.add(ch)
        best = max(best, right - left + 1)
    return best

Why the amortised cost is linear despite the nested loop: each iteration of the inner while removes one character and advances left by one. Since left never decreases and is bounded by n, the inner loop body executes at most n times summed across the entire outer loop. Total work is therefore O(n), not O(n^2). This is the standard amortised argument for sliding windows and it is worth saying explicitly, because an interviewer who sees a loop inside a loop will want to hear it. The pattern is generalised in the sliding window. The remaining inefficiency is in the constant, not the exponent: on a string such as "abcdefghij" * 5000, every repeat drags the left edge through nine removals one at a time, so the algorithm does roughly twice the pointer work of the version below while touching the set on every step. Both are O(n), and only one of them avoids the inner loop entirely. That gap is worth closing, because the fix also removes a whole category of bug: with no inner loop there is no possibility of the shrink condition and the window contents disagreeing.

Approach 3 - Sliding window with last-seen indices: O(n) time, one pass, no inner loop

The optimal formulation. The left edge teleports instead of walking.

def length_of_longest_substring(s):
    last_seen = {}          # char -> most recent index
    left = best = 0

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

    return best

Why the jump is safe: if ch last appeared at index p inside the current window, then every window ending at right and starting at or before p contains two copies of ch and is invalid. The earliest legal start is therefore p + 1, and moving left there in one step skips exactly the positions that were provably doomed. Nothing is lost because none of the skipped windows could have been answers.

Why the >= left guard is not optional: the map records the last occurrence anywhere in the string, including occurrences that have already fallen out of the window. On "abba", by the time right reaches the final a, left has already advanced to 2, while last_seen['a'] is still 0. Without the guard, left would be set to 1, moving backwards, and the window would silently readmit the duplicate b. The reported answer becomes 3 instead of 2. This single comparison is the most common bug in the problem.

Why best updates every iteration: after the possible jump, the window is valid by construction, so its length is a legitimate candidate. Deferring the update to the end of some conditional branch means windows that never triggered a jump are never measured, and the answer comes back too small on strings with no repeats at all.

Why the space bound has a min in it: the map stores one entry per distinct character currently tracked, which cannot exceed the alphabet size m nor the string length n. For ASCII input the map never exceeds 128 entries, so it is constant in practice, and the honest bound for arbitrary Unicode is O(min(m, n)).

Worked trace on "abba"

Complexity comparison

Edge cases to verify

• Empty string: returns 0. The loop never runs and best keeps its initial value.
• All identical: "bbbbb" returns 1. left jumps on every character and the window is never longer than one.
• All distinct: "abcdef" returns 6. No jump ever fires, which is why best must be updated unconditionally.
• Stale index: "abba" returns 2. Drop the >= left guard and this returns 3.
• Non-letter characters: "a b!a" treats space and punctuation as ordinary characters. Any solution using a 26-slot array indexed by ord(c) - ord('a') reads out of bounds here.

Where beginners go wrong

• Omitting the last_seen[ch] >= left guard. The map remembers occurrences that have already left the window, so an unguarded jump can move left backwards and readmit a duplicate. "abba" is the four-character input that exposes it, and nothing shorter does.
• Walking the left edge instead of jumping it. Removing one character at a time is correct and amortised linear with a set, but people who mix the two, keeping an index map yet still stepping left forward in a loop, get the worst of both: extra memory and no speed-up.
• Using a set when you need positions. A set answers membership only. The whole optimisation rests on knowing where the previous occurrence was, so the container has to be a map. The choice of data structure is the algorithmic decision here.
• Updating best only inside the shrink branch. On a string with no repeats the branch never fires and the function returns 0. Measure the window on every iteration, after the possible jump.
• Confusing substring with subsequence. On "pwwkew" the answer is 3 from "wke", not 4 from "pwke". Substrings are contiguous; a solution that drops characters is answering a different and much harder question.
• Assuming a 26-letter alphabet. The constraints allow digits, symbols and spaces. Indexing a fixed array by ord(c) - ord('a') produces negative indices for space and punctuation, which in Python reads silently from the wrong end of the array rather than crashing.

Interview follow-ups to expect

• "Return the substring, not its length." Record the start index alongside best whenever the best improves, then slice at the end. One extra variable, no change to the loop.
• "Allow at most k distinct characters." The invariant changes from "no repeats" to "at most k distinct", so the window needs counts rather than last-seen indices. Shrink from the left while the map holds more than k keys. Same skeleton, different invariant, which is the point of the exercise.
• "Allow each character to repeat at most twice." Again counts, shrinking while any count exceeds two. Once you see that the window is defined by a predicate over its contents, all of these are one template.
• "Longest substring with all characters the same after at most k replacements." The predicate becomes window_length - max_frequency <= k. Maintaining the running maximum frequency is the only subtlety, and it need never decrease for the algorithm to stay correct.
• "What if the input is a stream you cannot index?" The index-jump version needs absolute positions, which a stream can still supply as a running counter. Memory stays O(alphabet), so this works unchanged on unbounded input.
• "Make it work on Unicode grapheme clusters." Iterate over clusters rather than code points, since an emoji with a modifier is several code points but one user-perceived character. The algorithm is untouched; the tokenisation is the work.

Related reading

• The Sliding Window: the general template, and how to decide which pointer restores the invariant.
• Strings: the module this belongs to, including why alphabet size so often replaces input size in the space bound.
• Minimum Window Substring: the same machinery aimed at the shortest valid window instead of the longest, which flips when you shrink and when you record.