Minimum Window Substring

Problem

You are given two strings, a source s and a pattern t. Find the shortest contiguous substring of s that contains every character of t with at least the multiplicity it has in t (so if t has two As, the window needs two As). Return that substring, or an empty string if no such window exists. If several windows tie for the shortest length, return the leftmost one.

• s has at most 100,000 characters; t has at least one and at most as many as s.
• Both strings are made of English letters, either case.

Examples

• s = "XQYAZQBYXA", t = "AQX" → "XQYA". The first four characters already cover one X, one Q, and one A; no shorter span does.
• s = "timetable", t = "ttb" → "timetab". Two ts are required, so the window must stretch from the first t to the b.
• s = "zzz", t = "zzzz" → "". Four zs are needed and only three exist.

Hints

1. If a window contains everything in t, does extending it to the right ever break that? Does trimming it from the left?
2. Track how many characters of t are currently satisfied, so you can tell in O(1) whether the window is valid without rescanning counts.
3. Expand hi until the window is valid, then contract lo while it stays valid, recording the best; a need map plus a count of fully satisfied characters drives both moves.