Find the shortest stretch of s holding every letter of t. Grow the window right until it's complete, then shrink from the left while it stays so.
▼The problem
LeetCode 76 (Hard). Given strings s and t, return the shortest substring of s that contains every character of t, duplicates included, or "" if there is none.
Example: s = "ADOBECODEBANC", t = "ABC" → "BANC".
The solution
from collections import Counter
def minWindow(s, t):
need = Counter(t)
have, formed = Counter(), 0
best, left = "", 0
for right, ch in enumerate(s):
have[ch] += 1
if have[ch] == need[ch]:
formed += 1
while formed == len(need):
if not best or right - left + 1 < len(best):
best = s[left:right + 1]
out = s[left]
have[out] -= 1
if have[out] < need[out]:
formed -= 1
left += 1
return bestTranscript
Minimum Window Substring. Given strings s and t, return the shortest piece of s that contains every letter of t, repeats included, or the empty string if there's none.
Take this thirteen letter string, and t equals A, B, C. The first six letters hold all three, but the shortest window is B, A, N, C: four letters.
The simple way: try every start and every end, and count the letters in each window. With m letters, that's about m squared windows, each needing a count. Too slow.
Instead, slide one window. Track the counts t needs, and how many letters are covered. Stretch the right edge until all are. Then pull the left edge in while it still covers t, saving the shortest. When it breaks, stretch again.
In code, count t's letters. Add each right letter; if its count just reached the need, one more letter is formed. While all are formed, save the window if it's shorter, drop the left letter, and if that falls short, formed goes down.
Let's run it. Stretch right: A, B, then C at index five. Covered: save six. Pull left, and losing A breaks it. Stretch to the next A, at index ten. Pull left past D, O, B and E, until losing C. Stretch to the last C, then pull left: seven, six, five, four. B, A, N, C!
Each letter enters the window once and leaves at most once: order m plus n time, counting t too. The counts hold one entry per distinct letter: order k space.
Stretch to cover, shrink to the shortest, repeat. That's Minimum Window Substring.