76. Minimum Window Substring
You are given two strings s and t, both made of uppercase and lowercase English letters. Find the shortest contiguous substring (window) of s that contains every character of t, counting multiplicity — if t holds two 'a's, a valid window must hold at least two 'a's.
Return that window as a string. To keep the answer unique: if several windows tie for the shortest length, return the leftmost one, and if s contains no valid window at all, return the empty string (the judge prints it as -1).
Matching is case-sensitive. The classic follow-up: can you solve it in time linear in |s| + |t|?
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the shortest stretch of s holding an 'A', a 'B', and a 'C'.
Example 2:
Input: s = "a", t = "aa"
Output: "" (no window — printed as -1)
Explanation: t needs two 'a's but s only has one, so no window can cover t.
Constraints:
- 1 ≤ s.length, t.length ≤ 10⁵
- s and t consist of uppercase and lowercase English letters
- Matching is case-sensitive: 'A' and 'a' are different characters
Hints:
A window is valid when, for every character c of t, the window contains at least as many copies of c as t does. Frequency counts make that check cheap — you never compare strings directly.
Slide two pointers over s: advance the right end until the window becomes valid, then advance the left end while it stays valid. Each character enters and leaves the window at most once.
Keep a single `missing` counter — how many required characters (with multiplicity) the window still lacks. Updating it as characters enter/leave makes the validity test O(1) instead of rescanning 52 counts.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "ADOBECODEBANC", t = "ABC"
Expected output: "BANC"