Example 1
ready- Input
s = "ADOBECODEBANC" t = "ABC"- Expected
"BANC"- Why
- the final four characters supply the unique shortest cover
Minimum Window Substring
50 min · minWindow()A search result can contain every word you asked for and still be frustratingly broad. Your job here is to keep trimming until one more cut would lose something essential.
Given strings s and t, return the shortest substring — one unbroken slice of
s — that contains every character required by t.
A few ground rules:
- Character counts matter. Multiplicity means how many copies of a character are
required: if
tcontains twoAs, the chosen slice needs twoAs too. - Uppercase and lowercase characters are different.
- If no slice can satisfy
t, return the empty string"". - Whenever an answer exists in these tests, its shortest valid slice is unique.
Constraints
1 <= s.length <= 100_0001 <= t.length <= 100_000sandtcontain only lowercase and uppercase English letters.
Hints
Prove the direct version first
Choose each possible starting position, extend right, and stop when the current slice has every required count. Keep the shortest result you find.
Separate valid from minimal
Moving the right edge can make a slice valid. Once it is valid, moving the left edge asks a different question: how much can you discard before it becomes invalid?
Count satisfied character kinds
Store the required count for each character. A character kind becomes satisfied exactly when its window count reaches that requirement, and unsatisfied when its count drops below it.
Follow-up
Could you process s as a stream while keeping only the characters that still belong
to the current candidate window?
Visible cases
Examples
Example 2
ready- Input
s = "teamwork" t = "Z"- Expected
""- Why
- s contains no uppercase Z, so no window can qualify
Example 3
ready- Input
s = "aBac" t = "caBa"- Expected
"aBac"- Why
- every character is needed, including both copies of a
Interview signal
Asked at
AmazonMetaGoogleUber
Brute force — grow from every start
Pick a left edge, then extend the right edge until the slice covers every required character count. That first valid end is the shortest answer for this particular left edge, so you can compare it with the best result and move to the next start.
def min_window(s: str, t: str) -> str:
need: dict[str, int] = {}
for char in t:
need[char] = need.get(char, 0) + 1
best_start = 0
best_length = len(s) + 1
for left in range(len(s)):
window: dict[str, int] = {}
missing = len(t)
for right in range(left, len(s)):
char = s[right]
if char in need:
previous = window.get(char, 0)
if previous < need[char]:
missing -= 1
window[char] = previous + 1
if missing == 0:
length = right - left + 1
if length < best_length:
best_start = left
best_length = length
break
if best_length > len(s):
return ""
return s[best_start:best_start + best_length]Let n = len(s), m = len(t), and Σ be the number of distinct required character
kinds. Time O(n² + m), space O(Σ) — each left edge may scan almost all the way
to the end, while the maps track only characters from t.
Expand + contract — make each edge earn its move
A sliding window is a contiguous range whose edges move forward instead of restarting
from every position. Expand right until the range is valid. Then advance left while
it stays valid, recording each improvement before removing the next character.
The useful shortcut is to count satisfied character kinds. need_kinds never changes.
have_kinds rises only when a window count reaches its target, and falls only when a
removal takes that count below its target. The window is valid exactly when those two
numbers match.
def min_window(s: str, t: str) -> str:
required: dict[str, int] = {}
for char in t:
required[char] = required.get(char, 0) + 1
window: dict[str, int] = {}
need_kinds = len(required)
have_kinds = 0
left = 0
best_start = 0
best_length = len(s) + 1
for right, char in enumerate(s):
if char in required:
window[char] = window.get(char, 0) + 1
if window[char] == required[char]:
have_kinds += 1
while have_kinds == need_kinds:
length = right - left + 1
if length < best_length:
best_start = left
best_length = length
removed = s[left]
if removed in required:
if window[removed] == required[removed]:
have_kinds -= 1
window[removed] -= 1
left += 1
if best_length > len(s):
return ""
return s[best_start:best_start + best_length]Every character enters the range once through right and leaves at most once through
left. Time O(n + m), space O(Σ).
The core move is worth remembering: expand to restore validity, then contract to expose the best valid answer ending at that right edge.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
"BANC"
Run: visible + custom · Submit: full suite