Minimum Window Substring

Given strings s and t, return the shortest contiguous substring of s that contains every character from t with at least the same multiplicity. If no such substring exists, return the empty string. If several windows have the same minimum length, returning any one of them is acceptable — the supplied tests use unique answers.

Input / output

• Input: s: string, t: string
• Output: the minimum covering substring, or "" if impossible

Examples

1. s = "ADOBECODEBANC", t = "ABC" returns "BANC".
2. s = "a", t = "a" returns "a".
3. s = "a", t = "aa" returns "" because s does not contain two a characters.

Constraints

• 1 <= t.length <= s.length <= 10^5 for the canonical problem
• s and t may contain uppercase letters, lowercase letters, and digits

Target complexity

• Aim for O(|s| + |t|) time and O(|alphabet|) extra space.

Hints

1. Count how many of each character t needs before you scan s.
2. Expand a right pointer until the window is valid, then shrink the left pointer as far as possible while keeping it valid.

Follow-up How would you adapt the technique if the requirement were "cover all characters from t in order" instead of with arbitrary order?