Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
- m == s.length
- n == t.length
- 1 <= m, n <= 10⁵
- s and t consist of uppercase and lowercase English letters
s = "ADOBECODEBANC", t = "ABC""BANC"s = "a", t = "a""a"s = "a", t = "aa"""You want the shortest stretch of s that covers everything in t — every character of t, counting duplicates (if t is "aab" the window needs two a's and a b). Return that stretch as a string, or "" if none exists. Because we want the shortest valid window, this is the shortest-window Variable Sliding Window, the same shape as Minimum Size Subarray Sum: expand until valid, then squeeze from the left while it stays valid, recording the smallest. The hard part is not the window — it is deciding, cheaply, when the window is "valid".
Checking every substring and comparing its letter counts to t is around O(m² · alphabet) — endlessly re-counting overlapping ranges.
Build need, the count of each character t demands, and let required = len(need) be how many distinct characters must be satisfied. As the window grows, keep have, the window's own counts, and a single number formed: how many distinct required characters currently have enough copies in the window. The window is valid exactly when formed == required. The beauty is that formed updates in O(1) — a character entering can push one requirement from not-quite to just-met (formed += 1), and a character leaving can push one back below its quota (formed -= 1). No rescanning.
from collections import Counter
def minWindow(s, t):
if not s or not t: return ""
need = Counter(t)
required = len(need)
have = {}
formed = 0
left = 0
best_len = float('inf')
best_start = 0
for right in range(len(s)):
c = s[right]
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]: # this char just reached its quota
formed += 1
while formed == required: # valid - record, then squeeze
if right - left + 1 < best_len:
best_len = right - left + 1
best_start = left
lc = s[left]
have[lc] -= 1
if lc in need and have[lc] < need[lc]: # dropped below quota
formed -= 1
left += 1
return "" if best_len == float('inf') else s[best_start:best_start + best_len]formed counts distinct satisfied requirements, not raw characters. We bump it only when a character's count hits exactly its needed amount (have[c] == need[c]) — not on every occurrence — otherwise extra copies of the same letter would over-count and the window would look valid too early. Symmetrically, on the left we drop formed only when a count falls below its quota, so surplus copies leave harmlessly. And note case matters: 'A' and 'a' are different requirements.If t needs more of a letter than s can offer (s = "a", t = "aa"), formed never reaches required, best_len stays infinite, and we return "".
The four slots: (a) invalid = formed < required (so we squeeze while formed == required); (b) expand bumps have and maybe formed; (c) shrinking decrements have and maybe drops formed; (d) record the minimum window, inside the squeeze loop while still valid — the shortest-window timing you first saw in Minimum Size Subarray Sum. The reusable lesson is the formed/required counter: whenever "valid" means satisfying several requirements at once, don't re-check them all each step — track how many are currently satisfied and nudge that one number as characters cross their thresholds.
Min Window Substring
Expansion & Contraction
This is the ultimate sliding window challenge. Expand right to satisfy all frequency requirements, then contract left to find the absolute minimum valid span.
Step-by-Step Logic
Step 1: First window found! [ADOBEC] contains all target chars {A, B, C}. Size 6.