Minimum Window Substring

Problem

A log aggregation system needs to find the shortest contiguous sequence of log entries that references every required event type. Given a source string s and a target string t, return the minimum window substring of s that contains every character in t (including duplicates). Return an empty string if no such window exists.

Example 1:

Input: s = "YDEXBYXODB", t = "XBD"
Output: "DEXB"
Explanation: the minimum window containing an X, a B, and a D is "DEXB".

Example 2:

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

Example 3:

Input: s = "z", t = "zz"
Output: ""
Explanation: t needs two 'z's but s has only one, so no window exists.

Constraints:

• m == s.length, n == t.length
• 1 <= m, n <= 10^4
• s and t consist of uppercase and lowercase English letters.

Solution Breakdown

Approach: Variable-size minimum window with two frequency Counters.

Keep two Counters: t_count (the fixed requirement) and window_count (the current window's character frequencies). Grow the window right by adding s[end] to window_count. After each add, check whether window_count >= t_count - Python's Counter supports this comparison directly, meaning every character in t_count has at least the required count in window_count. While the window still covers t, record the window if it beats best_len, then shrink from the left by decrementing window_count[s[start]] and advancing start. The while loop exits when the window no longer covers t, and you go back to expanding right.

In JS/TS there's no built-in Counter comparison, so a small covers(w, t) helper iterates t and checks each count - same logic, explicit.

Trace s="YDEXBYXODB", t="XBD": the window first covers at "YDEXB", then later shrinks to "DEXB" (length 4), the answer.

Edge cases: Empty s or t returns "". When t demands more copies than s has (e.g. s="z", t="zz") the window never covers, so best_len stays infinite and the function returns "".

Complexity: O(|s| + |t|) time - each pointer crosses s at most once; the covers check in JS/TS touches at most |t| distinct chars but the total across all iterations is still O(|s|) amortized since each char enters and leaves the window once. O(|s| + |t|) space for the two frequency maps.