Visualization

Complexity

How It Works

1. 1Build frequency map need[] from t. Set required = distinct char count in t
2. 2Advance right pointer, add s[right] to have[]. If have[c] == need[c]: formed++
3. 3While formed == required: record window if it beats the minimum, then advance left (remove s[left], decrement formed if needed)
4. 4Repeat until right reaches end of s
5. 5Return the shortest valid window recorded, or "" if none found

Key Insight: formed counter

• •Instead of scanning the whole window for validity, track how many distinct characters from t are fully satisfied (have count ≥ need count)
• •formed increments only when have[c] exactly reaches need[c] — not on every addition
• •This makes validity check O(1) per pointer move instead of O(m)

Active Recall Quiz