Hints — p30 Minimum Window Substring

Read one at a time.

Hint 1 — Multiplicity matters. t="AABC" means the window needs at least TWO 'A's, one 'B', one 'C'. Use Counter, not set.

Hint 2 — Expand then contract template. Two pointers left, right. Expand right until the window is VALID (contains all required chars with multiplicity). Then contract left while it stays valid, recording the tightest. Repeat.

Hint 3 — How to check validity efficiently. Naive: for k,v in need: if have[k] < v: return False. O(σ) per check, called O(N) times → O(N·σ). Works, but…

The trick: maintain formed = count of distinct chars in t currently SATISFIED (have[c] >= need[c]). When formed == required (= len(need)), window is valid. O(1) check.

Hint 4 — Maintaining formed correctly. On EXPAND (adding char c): have[c] += 1; if c in need and have[c] == need[c]: formed += 1. Critical: use ==, not >=. We increment exactly once per char, at the moment we first meet the need.

On CONTRACT (removing char c): check if c in need and have[c] == need[c]: formed -= 1 BEFORE have[c] -= 1. We lose a match the moment we go below.

Hint 5 — Don’t slice inside the loop. Track (best_l, best_len); slice once at the end. s[left:right+1] in the loop is O(N) per step → kills your O(N) bound.

Edge: best_len = inf initially. Return "" if still inf at the end.

If still stuck: solution.py has the canonical match-counter and the naive O(N·σ) for comparison. Read the INVARIANT comment above formed in min_window.