Minimum Window Substring

hardSliding Windowexpand/shrink window with need vs have countsB75Solve on LeetCode#76

Part of Practice: Counted Windows & Deques

Given strings s and t, return the shortest substring of s that contains every character of t, including duplicates — if t has two a's, the window must too. If no such substring exists, return the empty string. The answer is guaranteed unique when it exists.

Both strings can be up to 10^5 characters, so the O(n^2) scan over all windows is out; the expected solution is linear.

Examples

Input:: s = "ADOBECODEBANC", t = "ABC"
Output:: "BANC"

"BANC" contains A, B, and C and is the shortest such stretch. "ADOBEC" also qualifies but is longer.

Input:: s = "a", t = "a"
Output:: "a"

The whole string is the window.

Input:: s = "a", t = "aa"
Output:: ""

t needs two a's but s only has one, so no window works. Duplicates in t must be fully covered.

Hints

One at a time — struggle first, peek second.

Your thinking space — verify on LeetCode, then mark it.