LeetCode 3 · Sliding Window

Longest Substring Without Repeating Characters, explained with a picture

A train window over shop signs.

MediumSliding Window
▶ Watch it step by step

The problem

Given a string, find the length of the longest stretch of consecutive characters with no repeated letter.

Input:  "abcabcbb"
Output: 3   ("abc")

Picture it

Picture yourself looking out of a train window at a street of shop signs, one letter per shop. The window can stretch and shrink. Its right edge moves forward one shop at a time. If the new letter is already somewhere inside the window, the left edge jumps just past that earlier copy, so the window again has only unique letters. We record the widest window we ever had.

How to recognise it

  • The answer is a substring (a contiguous run of characters), not a subsequence where you may skip characters.
  • You want the longest (or shortest) run that satisfies a rule, here "no character appears twice".
  • The rule is monotone: if a window breaks it, every bigger window containing it breaks it too. So you can grow on the right and shrink on the left.
  • The rule depends on what is inside the window, which a dictionary can track as it moves.
  • Lengths up to about 5 × 10^4 rule out checking every substring.

Start with brute force

From every starting position, extend to the right with a set of letters seen so far, and stop at the first repeat. The longest run found is the answer.

def longest_brute(s):
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
        best = max(best, len(seen))
    return best

Time is O(n · m), where m is the length of the answer (at most n). When most characters differ, as in long Unicode text, that is O(n²): for n = 5 × 10^4 about 1.25 × 10^9 steps. Space is O(m) for the set.

From brute force to the idea

  1. Find the waste. After a repeat, the next start throws the set away and re-reads characters it has just checked.
  2. Keep the window. Hold a window from left to right that always has unique letters. right moves forward one character at a time.
  3. Fix a repeat by moving left. If the new character ch is already inside the window, any window starting at or before that earlier copy contains ch twice. So left jumps to just past it.
  4. Remember positions. A dictionary last maps each letter to where it last appeared, so the jump is one lookup, not a scan.
  5. Ignore copies outside the window. A letter can be in last but sit left of left. That is why the code checks last[ch] >= left before jumping.
  6. Record the best. After each step the window right - left + 1 is valid, so compare it with the best so far.

This is the key idea: a sliding window plus a "last seen position" dictionary, with the left edge jumping past the old copy.

The key idea

Sliding window + “last seen position” dictionary: when a repeat appears, jump the left edge past the old copy. O(n).

Python solution

def longest_unique(s):
    last = {}                 # letter -> last position
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n · m), up to O(n²): each start re-scans up to m charactersO(m): the set holds one run
Sliding window (shown code)O(n): right visits each character once and left only moves forwardO(k): one entry per distinct character, k ≤ n

Edge cases

  • Empty string: the loop never runs and the code returns 0.
  • One character ("a"): returns 1.
  • All the same ("bbbbb"): left follows right, so the answer is 1.
  • Old copy outside the window ("abba"): returns 2. Without the last[ch] >= left check, the second a would move left backwards and the code would wrongly return 3.
  • Spaces, digits and case: every character counts, and "a" differs from "A". "aA" returns 2 and "a b c a" returns 3 (the space repeats).
  • Answer at the very end ("tmmzuxt"): returns 5 because best is updated on every step, not only when a repeat appears.

Common mistakes

  • Dropping the last[ch] >= left check, so left jumps backwards on strings like "abba".
  • Updating best only when a repeat is found, which misses a longest run that reaches the end of the string.
  • Clearing a set on a repeat, which forgets the letters between the old copy and the new one.
Your turn: at most two kinds of letter

Find the length of the longest substring that contains at most two distinct characters. For "eceba" the answer is 3 ("ece"), and for "ccaabbb" it is 5 ("aabbb"). Describe your approach, then write it if you like.

Compare with our answer

Same window, different rule. Grow right and count letters inside the window. When there are more than two kinds, shrink from the left one step at a time until two remain. A single jump does not work, because you do not know in advance how far left must move.

def longest_two_distinct(s):
    count = {}                    # letter -> how many times inside the window
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > 2:     # too many kinds: shrink from the left
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]
            left += 1
        best = max(best, right - left + 1)
    return best

Time O(n), because each character enters and leaves the window at most once. Space O(1) here, as the dictionary never holds more than three keys.

A strong answer mentions: counts instead of last positions, deleting a letter when its count reaches 0, and why the inner while loop does not make it O(n²).

Check what stuck

1. Given a list of positive numbers, find the shortest contiguous run whose sum is at least a target. Which approach fits?

2. Why is the shown solution O(n) even though left can jump many places at once?

3. A learner deletes and last[ch] >= left from the shown code. What does it return for "abba"?

Score 60% or more and the lesson is marked complete.