Problem Statement
Minimum Window Substring
You get two strings, s and t. Find the shortest piece of s that contains every letter in t, counting duplicates. For example, if t has two A's, your piece of s must also have at least two A's. If no piece of s works, return the empty string "".
Signals to notice
Brute force first
Check every substring of s for containing all characters of t. Each substring is checked independently. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
Sliding window with two pointers: expand right to include characters, shrink left to minimize length while still containing all of t. Track character counts and a 'formed' counter. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on s="ADOBECODEBANC", t="ABC"
need={A:1,B:1,C:1}, target=3 distinct chars; have=0, left=0, best=""
right=0..5 expand "ADOBEC": A,B,C each hit required count -> have=3 (valid)
have==3: best="ADOBEC" (len 6); shrink left past A -> window A<1, have=2, left=1
right=6..10 expand to "DOBECODEBA": second A added, have back to 3 (valid)
shrink: drop D,O,B... "CODEBA" then "ODEBA" loses C, have=2; best still "ADOBEC"? no -> "CODEBA" len6 not smaller
right=11 add N, right=12 add C: window "...BANC" has A,B,C, have=3 (valid)
have==3: shrink to "BANC" (len 4 < 6) -> best="BANC"; further shrink loses B, have=2
loop ends, return best="BANC"What must stay true
The window is valid when it contains at least as many of each character as t requires. Expand to make it valid, shrink to minimize it, and track the smallest valid window seen. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
need = count(t); have = 0; window = {}; best = ""; left = 0
for right, c in s:
window[c]++; if window[c] == need[c]: have++
while have == len(need):
update best if (right-left+1) is smaller
window[s[left]]--; if window[s[left]] < need[s[left]]: have--; left++
return bestPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Comparing full frequency maps at every step — track a 'formed' count that increments when a character's window frequency meets its required frequency. This makes each step. The fix is usually to return to the meaning of each move, not just the steps themselves.