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
- Find the waste. Each start recounts letters that the previous start had already counted.
- One window, two edges. Move
rightforward, adding letters tohave. When the window coverst, moveleftforward to shrink it while it still does. - Keep one number for "covered".
missingstarts atlen(t). A new letter lowers it only ifhave[ch]was still belowneed[ch], so extra copies do not count. The window coverstexactly whenmissing == 0, an O(1) check instead of comparing 52 counts. - Record, then shrink. While
missing == 0, the window is valid: record it if it is the shortest yet. Then removes[left]. If that drops a needed letter below its count,missinggoes up and the shrinking stops. - Return the best.
beststays""if no window ever coveredt.
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 bestLeetCode 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(52 · n²): every start scans right and checks all counts | O(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 length | O(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""; oneais not enough. - Exact fit (
"aa","aa"): returns"aa". - Case matters (
"abc","A"): returns"";Aandaare 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 raisesIndexError, becausemissingis 0 from the start andleftruns past the end ofs. - Missing import: the code needs
from collections import Counter; without it the call raisesNameError.
Common mistakes
- Lowering
missingfor every letter oftthat enters, even surplus copies. Then"AAB"witht = "AB"returns"A". - Comparing two whole Counters on every step instead of using
missing, which multiplies the work by the alphabet size. - Raising
missingwhenever a letter oftleaves, even when the window still has more than enough of it. - Recording the window after shrinking, when it may no longer be valid.
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.
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?
The best stretch can have any length, and covering only gets easier as it grows, so a variable window with a "missing" counter fits. Sorting loses the order of the log, and a fixed size of 5 assumes no other products in between.
2. Why does the shown code track missing instead of comparing have with need?
Comparing two Counters looks at every key, up to 52 here, on every step. missing is updated by at most one per letter that enters or leaves, so the check is one comparison with 0.
3. A learner changes if have[ch] < need[ch]: to if ch in need:. Which call now returns a wrong answer?
Now the second A also lowers missing, so it hits 0 before any B arrives, and the code reports "A". The other inputs never have a surplus copy enter while missing is still above 0.
Score 60% or more and the lesson is marked complete.