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.

Input: s = "ADOBECODEBANC", t = "ABC"  → "BANC"
Input: s = "a",             t = "a"    → "a"
Input: s = "a",             t = "aa"   → ""

Solution

Approach: Variable-size minimum window with a have/need match counter.

Grow the window until it covers every character of t, then shrink it from the left while it still covers t to find the smallest such window. t_count = Counter(t) holds the requirement, and need = len(t_count) is the number of distinct characters that must each reach their required count. A running have tracks how many distinct requirements are currently met. For each end, add s[end] to window_count; if that character is in t and its window count just reached t_count[char], increment have. Whenever have == need the window is valid, so enter the shrink loop: record the window if it beats best_len, then remove s[start], and if that drops a required character below its quota decrement have, and advance start. Recording happens inside the shrink loop because each valid-and-shrinking state is a candidate for the minimum - this is the opposite of longest-window problems, which record after shrinking restores validity. Tracking (best_len, best_left) indices instead of slicing each step avoids O(window) copies; you slice once at the end.

Trace s="ADOBECODEBANC", t="ABC": the window first becomes valid at "ADOBEC", then later shrinks to "BANC" (length 4), the answer.

Edge cases: Empty s or t returns "". When t demands more copies than s has (e.g. s="a", t="aa") have never reaches need, so best_len stays infinite and the function returns "".

Complexity: O(|s| + |t|) time, O(|s| + |t|) space - each pointer crosses s at most once; the two frequency dicts are bounded by the alphabet in practice.