LeetCode 76 · Sliding Window

Minimum Window Substring, explained with a picture

The smallest net that catches every fish.

HardSliding Window
▶ Watch it step by step

The problem

Given a string s and a string t, find the shortest stretch of s that contains every character of t (including repeats). Return "" if none exists.

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Picture it

Picture fish swimming down a river in a line, each fish a letter. You need a net that catches at least one A, one B and one C. Stretch the net’s right edge until every needed fish is inside. Then pull the left edge in as far as you can while still holding all of them. Record that size, then keep going.

How to recognise it

  • You want the shortest contiguous stretch that contains everything on a list, with repeats counted.
  • The rule is monotone: if a window contains all of t, so does every bigger window around it. So you can grow on the right until it works, then shrink from the left while it still works.
  • "Contains all of t" is a question about counts, which a dictionary can track as letters enter and leave.
  • Both strings have up to 10^5 upper- and lowercase letters, so checking every substring is far too slow.

Start with brute force

From every start, extend right until the window covers t, then stop: a longer window from that start cannot be shorter.

from collections import Counter

def min_window_brute(s, t):
    need = Counter(t)
    best = ""
    for i in range(len(s)):
        have = Counter()
        for j in range(i, len(s)):
            have[s[j]] += 1
            if all(have[c] >= need[c] for c in need):
                if not best or j - i + 1 < len(best):
                    best = s[i:j + 1]
                break
    return best

Each start can scan to the end, and each check looks at up to 52 letters, so time is O(52 · n²) in the worst case. With n = 10^5 that is about 5 × 10^11 steps. Space is O(1) for the counts (at most 52 letters).

From brute force to the idea

  1. Find the waste. Each start recounts letters that the previous start had already counted.
  2. One window, two edges. Move right forward, adding letters to have. When the window covers t, move left forward to shrink it while it still does.
  3. Keep one number for "covered". missing starts at len(t). A new letter lowers it only if have[ch] was still below need[ch], so extra copies do not count. The window covers t exactly when missing == 0, an O(1) check instead of comparing 52 counts.
  4. Record, then shrink. While missing == 0, the window is valid: record it if it is the shortest yet. Then remove s[left]. If that drops a needed letter below its count, missing goes up and the shrinking stops.
  5. Return the best. best stays "" if no window ever covered t.

This is the key idea: grow until covered, shrink while covered, and track coverage with one missing counter.

The key idea

Expand right until the window is valid, then shrink left while it stays valid, tracking the smallest. A “have vs need” counter makes each check O(1). Each character of s enters and leaves the window at most once, so the whole thing is O(m + n) for m = len(s), n = len(t).

Python solution

def min_window(s, t):
    need, have = Counter(t), Counter()
    missing = len(t)
    best, left = "", 0
    for right, ch in enumerate(s):
        if have[ch] < need[ch]:
            missing -= 1
        have[ch] += 1
        while missing == 0:   # net has all
            size = right - left + 1
            if not best or size < len(best):
                best = s[left:right + 1]
            have[s[left]] -= 1
            if have[s[left]] < need[s[left]]:
                missing += 1
            left += 1
    return best

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter

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(52 · n²): every start scans right and checks all countsO(1): at most 52 counts
Sliding window (shown code)O(m + n) pointer moves, as each edge only moves forward; each new shortest window is also copied, which adds at most its lengthO(1) for the counts, plus the copied answer

Here n is the length of s and m the length of t. Storing the best window's start and end, and slicing once at the end, avoids the copies.

Edge cases

  • Repeats in t (s = "a", t = "aa"): returns ""; one a is not enough.
  • Exact fit ("aa", "aa"): returns "aa".
  • Case matters ("abc", "A"): returns ""; A and a are different letters.
  • No window or empty s: returns "".
  • Ties: only a strictly shorter window replaces best, so the leftmost shortest window wins. LeetCode promises a unique answer.
  • Empty t: outside LeetCode's limits. The shown code then raises IndexError, because missing is 0 from the start and left runs past the end of s.
  • Missing import: the code needs from collections import Counter; without it the call raises NameError.

Common mistakes

  • Lowering missing for every letter of t that enters, even surplus copies. Then "AAB" with t = "AB" returns "A".
  • Comparing two whole Counters on every step instead of using missing, which multiplies the work by the alphabet size.
  • Raising missing whenever a letter of t leaves, even when the window still has more than enough of it.
  • Recording the window after shrinking, when it may no longer be valid.
Your turn: every kind of letter

Find the shortest substring of s that contains every distinct letter of s itself at least once. For "aabcbcdbca" the answer is "dbca". Describe your approach, then write it if you like.

Compare with our answer

t is now "one of each distinct letter", so count kinds instead of copies. need is the number of distinct letters in s. kinds goes up when a letter's count rises from 0 to 1, and down when it falls back to 0. Grow and shrink exactly as before.

from collections import Counter

def shortest_all_distinct(s):
    need = len(set(s))
    have = Counter()
    kinds, best, left = 0, "", 0
    for right, ch in enumerate(s):
        have[ch] += 1
        if have[ch] == 1:
            kinds += 1
        while kinds == need:
            if not best or right - left + 1 < len(best):
                best = s[left:right + 1]
            have[s[left]] -= 1
            if have[s[left]] == 0:
                kinds -= 1
            left += 1
    return best

Time O(n) pointer moves, space O(k) for k distinct letters.

A strong answer mentions: counting kinds rather than copies, changing the counter only on 0 to 1 and 1 to 0, and the same grow-then-shrink loop.

Check what stuck

1. A shop log lists product ids in order. You must find the shortest stretch of the log that includes at least one sale of each of 5 given products. Which approach fits best?

2. Why does the shown code track missing instead of comparing have with need?

3. A learner changes if have[ch] < need[ch]: to if ch in need:. Which call now returns a wrong answer?

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