{ }SolveLogs
⌕
Home / Sliding Window / #76
LeetCode #76 Hard

Minimum Window Substring

Minimum Window Substring is LeetCode 76 (Hard). You are given two strings s and t. Return the shortest substring of s that contains every character of t, including duplicates. If no such substring exists, return the empty string "".

  • "Including duplicates" means a character that appears k times in t must appear at least k times in the window.
  • The characters inside the window do not have to be in the same order as in t, and extra characters are allowed.
  • The answer is guaranteed to be unique.

Both strings can be 10⁵ characters long, so checking every substring is far too slow; the target is one linear pass.

Constraints
  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10⁵
  • s and t consist of uppercase and lowercase English letters.
sliding-windowstringshashingtwo-pointers
Open on LeetCode ↗
02

Intuition

Checking every substring of s is O(n²) substrings with an O(n) check each. One left-to-right pass is enough. Keep a sliding window s[left..right] (a stretch of s whose two ends only ever move right), because of one property:

  • if a window covers t, every larger window around it also covers t;
  • if a window does not cover t, no smaller window inside it does.

So the right end grows the window until it covers t, and the left end shrinks it while it still does. A small count of what is still missing answers "does it cover t?" in O(1).

How to spot this pattern

"Shortest (or longest) contiguous substring that satisfies a condition", where the condition gets easier to satisfy as the window grows, is a variable-size sliding window. Here the condition is "contains all of t". Related: longest substring without repeating characters, permutation in string, find all anagrams. Of that family, the minimum window substring LeetCode problem is the one rated Hard, because duplicates in t must be counted copy by copy.

03

Approach

Try it first

Before reading on: for s = "ADOBECODEBANC", move a right pointer until the window contains A, B and C. How far can you then move the left pointer? What single number tells you, without rescanning, whether the window still covers t?

Two ways to solve it

Sliding windowBest
Time O(m + n)Space O(1)

right grows the window until missing hits 0, then left shrinks it while it still covers t.

  • Passes: each character enters and leaves once.
  • Cover check: O(1) through missing.
  • Fits: the full 10⁵ limit.

The accepted answer, and the one interviewers expect.

Solution & demo ↓
Every start index
Time O(m²)Space O(1)

For each start i, extend an end pointer until the window covers t, and keep the shortest one found.

  • Passes: one fresh scan per start.
  • Cover check: the same missing counter.
  • Fits: short strings only.

A fine first idea, but it times out at m = 10⁵.

Code ↓

The scan from every start repeats work the sliding window keeps, so the window wins by a factor of m. The steps, code and live demo below follow the sliding window; the per-start code comes after the demo.

1

Count what t needs

need[c] = occurrences of c in t. missing = len(t). The best window starts empty (length infinity). need tracks each character's shortfall, and missing turns "does the window cover t?" into one comparison.

2

Expand with right

For each right, take ch = s[right]:

  • if need[ch] > 0, this copy is still required, so missing -= 1;
  • then need[ch] -= 1 either way; a negative value just means a surplus copy.

Only copies that were still required reduce missing.

3

Shrink while the window covers t

While missing == 0, the window covers t:

  • record it if it is the shortest so far, while it still covers t;
  • drop s[left] with need[s[left]] += 1;
  • if that value becomes positive, a required copy just left, so missing += 1;
  • move left forward.
4

Return the best window

If no window ever covered t, return ""; otherwise return s[best_start : best_start + best_len]. best_len stays infinite only if t could never be covered.

04

Minimum Window Substring solution in Python | C++ | Java

▶1class Solution:
▶2 def minWindow(self, s: str, t: str) -> str:
▶3 need = Counter(t)
▶4 missing = len(t)
▶5 best_len, best_start = float("inf"), 0
▶6 left = 0
▶7 for right, ch in enumerate(s):
▶8 if need[ch] > 0:
▶9 missing -= 1
▶10 need[ch] -= 1
▶11 while missing == 0:
▶12 if right - left + 1 < best_len:
▶13 best_len, best_start = right - left + 1, left
▶14 need[s[left]] += 1
▶15 if need[s[left]] > 0:
▶16 missing += 1
▶17 left += 1
▶18 if best_len == float("inf"):
▶19 return ""
▶20 return s[best_start : best_start + best_len]
sA0D1O2B3E4C5O6D7E8B9A10N11C12needA1B1C1missing3window0window empty · missing 3
needA:1 B:1 C:1copies still required
missing3window covers t when 0
Setup. need says how many copies of each character of t the window still lacks; missing is their total. The window starts empty, so it lacks all 3.
sA0D1O2B3E4C5O6D7E8B9A10N11C12needA0B0C0missing0window6missing 0 → window covers t
right5added 6 chars
needA:0 B:0 C:0after adding
missing0valid window
Expanding added "ADOBEC". Each character that was still needed lowered missing; extras only pushed their need below 0. Now missing = 0: the window "ADOBEC" contains all of t.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA1B0C0missing1window6best "ADOBEC" · drop A → missing 1
left0 → 1drop 'A'
best"ADOBEC"length 6
missing1window broken
The window "ADOBEC" covers t and is the shortest so far, so record it before shrinking. Dropping A removes a copy t needs (need[A] becomes 1), so missing rises to 1 and the window must grow again.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B-1C0missing0window10missing 0 → window covers t
right10added 5 chars
needA:0 B:-1 C:0after adding
missing0valid window
Expanding added "ODEBA". Each character that was still needed lowered missing; extras only pushed their need below 0. Now missing = 0: the window "DOBECODEBA" contains all of t.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B-1C0missing0window10drop D · still covers
left1 → 2drop 'D'
best"ADOBEC"length 6
missing0still 0
This window is valid but not shorter than the best, so nothing is recorded. Dropping D costs nothing: it is not in t. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B-1C0missing0window9drop O · still covers
left2 → 3drop 'O'
best"ADOBEC"length 6
missing0still 0
This window is valid but not shorter than the best, so nothing is recorded. Dropping O costs nothing: it is not in t. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B0C0missing0window8drop B · still covers
left3 → 4drop 'B'
best"ADOBEC"length 6
missing0still 0
This window is valid but not shorter than the best, so nothing is recorded. Dropping B costs nothing: the window had a spare copy. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B0C0missing0window7drop E · still covers
left4 → 5drop 'E'
best"ADOBEC"length 6
missing0still 0
This window is valid but not shorter than the best, so nothing is recorded. Dropping E costs nothing: it is not in t. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B0C1missing1window6drop C → missing 1
left5 → 6drop 'C'
best"ADOBEC"length 6
missing1window broken
This window is valid but not shorter than the best, so nothing is recorded. Dropping C removes a copy t needs (need[C] becomes 1), so missing rises to 1 and the window must grow again.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B0C0missing0window7missing 0 → window covers t
right12added 2 chars
needA:0 B:0 C:0after adding
missing0valid window
Expanding added "NC". Each character that was still needed lowered missing; extras only pushed their need below 0. Now missing = 0: the window "ODEBANC" contains all of t.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B0C0missing0window7drop O · still covers
left6 → 7drop 'O'
best"ADOBEC"length 6
missing0still 0
This window is valid but not shorter than the best, so nothing is recorded. Dropping O costs nothing: it is not in t. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 6needA0B0C0missing0window6drop D · still covers
left7 → 8drop 'D'
best"ADOBEC"length 6
missing0still 0
This window is valid but not shorter than the best, so nothing is recorded. Dropping D costs nothing: it is not in t. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 5needA0B0C0missing0window5best "EBANC" · drop E · still covers
left8 → 9drop 'E'
best"EBANC"length 5
missing0still 0
The window "EBANC" covers t and is the shortest so far, so record it before shrinking. Dropping E costs nothing: it is not in t. Keep shrinking.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 4needA0B1C0missing1window4best "BANC" · drop B → missing 1
left9 → 10drop 'B'
best"BANC"length 4
missing1window broken
The window "BANC" covers t and is the shortest so far, so record it before shrinking. Dropping B removes a copy t needs (need[B] becomes 1), so missing rises to 1 and the window must grow again.
sA0D1O2B3E4C5O6D7E8B9A10N11C12best · 4needA0B1C0missing1window4return "BANC"
result"BANC"
Done. The shortest window that covers t is "BANC". Both pointers only moved forward, so the whole scan is O(|s| + |t|).
05

Brute force from every start

For each start i, copy the counts of t and move an end pointer j until missing reaches 0. That s[i..j] is the shortest window starting at i, so stop there and compare it with the best so far.

▶1class Solution:
▶2 def minWindow(self, s: str, t: str) -> str:
▶3 need = Counter(t)
▶4 best = ""
▶5 for i in range(len(s)):
▶6 left = need.copy()
▶7 missing = len(t)
▶8 for j in range(i, len(s)):
▶9 if left[s[j]] > 0:
▶10 missing -= 1
▶11 left[s[j]] -= 1
▶12 if missing == 0:
▶13 if not best or j - i + 1 < len(best):
▶14 best = s[i : j + 1]
▶15 break
▶16 return best
06

Common pitfalls

Counting distinct characters instead of copies

✗ Wrong
missing = len(set(t))
✓ Right
missing = len(t)

With t = "AAB", a window holding one A and one B would be accepted. missing must count every required copy, and it only drops when a copy is still needed (need[ch] > 0).

Decrementing missing for surplus characters

✗ Wrong
need[ch] -= 1
missing -= 1
✓ Right
if need[ch] > 0:
    missing -= 1
need[ch] -= 1

Then every character counts toward t, even ones it does not contain or already has enough of. For "ADOBECODEBANC" the window "ADO" already brings missing to 0 and is returned, although it has no B or C.

Recording the window after shrinking

✗ Wrong
while missing == 0:
    ...  # drop s[left]
    left += 1
    best = min(best, right - left + 1)
✓ Right
while missing == 0:
    best = min(best, right - left + 1)
    ...  # then drop s[left]

After dropping s[left] the window may no longer cover t, so its length is not a valid answer. Record first, then shrink.

07

Edge cases

t longer than s

missing never reaches 0, so the best length stays infinite and "" is returned.

Upper and lower case

'a' and 'A' are different characters. A 128-entry array indexed by character code handles both without extra work.

08

Complexity

Time
O(m + n)
Space
O(1)
m = len(s), n = len(t). Counting t is O(n). right visits each character of s once, and left never passes right, so each character enters and leaves the window at most once. The count array has a fixed 128 entries.
09

Minimum Window Substring FAQ

How do you solve minimum window substring?
  • Counts: need[c] for each character of t, and missing = len(t).
  • Expand: move right; if need[s[right]] > 0, decrement missing; always decrement need[s[right]].
  • Shrink: while missing == 0, record the window, then remove s[left] (increment its need; if it becomes positive, increment missing) and move left.
  • Answer: the shortest recorded window, or "".
  • Complexity: O(|s| + |t|) time, O(1) extra space for a fixed alphabet.
What is the time complexity of minimum window substring?

O(|s| + |t|). Counting t is O(|t|); each character of s is added once by right and removed at most once by left. Space is O(1) for a fixed character set, or O(k) for k distinct characters with a hash map.

← Prev · #75
Sort Colors
Next · #77 →
Combinations