Min Window Substring LeetCode 76 Deep Dive

LeetCode 76 Minimum Window Substring gives you two strings s and t. Your task is to find the shortest contiguous substring of s that contains every character of t, including duplicates. If t is "AABC" you need a window in s with at least two A's, one B, and one C. If no such window exists, return an empty string.

The problem is a classic sliding window challenge. The window must cover all characters of t — not just unique characters, but the exact counts. A window missing even one required character is invalid. The goal is to minimize the window length over all valid windows found during the scan.

Constraints make brute force infeasible: s and t can each be up to 10^5 characters. An O(n^2) approach examining every possible window will time out. The O(n) sliding window solution uses two pointers and a frequency map to process each character at most twice.

The brute force approach checks every possible substring of s. For each pair of indices (i, j) where i <= j, extract s[i..j] and count whether it contains all characters of t with the required frequencies. This generates O(n^2) substrings and each frequency comparison takes O(m) time where m is the length of t, giving O(n^2 * m) total — far too slow.

A slight improvement pre-computes the frequency map of t once, then slides a window and maintains a running character count. But even this naive sliding approach does not shrink the window — it only expands, missing the key insight that once a valid window is found, you can try to shrink it from the left to find an even shorter valid window.

The fundamental problem with brute force is that it re-examines characters already seen. The two-pointer sliding window avoids this by processing each character of s at most twice: once when the right pointer includes it in the window, and once when the left pointer excludes it. This gives the O(n) guarantee.

Initialize a frequency map called need by counting every character in t. This tells you exactly how many of each character are required for a valid window. For example, if t is "AAOCP", need becomes {'A': 2, 'O': 1, 'C': 1, 'P': 1}. Also initialize a window map to track current character counts within the active window, and set both left and right pointers to 0.

A critical variable called formed tracks how many unique characters in t have been fully satisfied in the current window. A character c is satisfied when window[c] >= need[c]. Once formed equals the total number of unique characters in need (call it required), the window is valid and contains all characters of t with correct counts.

The right pointer expands the window one character at a time. Each time s[right] is added, increment window[s[right]]. If s[right] is in need and window[s[right]] now equals need[s[right]], increment formed — that character's requirement is newly met. Repeat until right reaches the end of s or formed equals required.

Once formed equals required, you have a valid window. Now try to shrink it from the left to find a potentially shorter valid window. Increment left, decrementing window[s[left]] as that character leaves. If s[left] is in need and window[s[left]] drops below need[s[left]], decrement formed — that character's requirement is no longer met. Continue shrinking as long as formed equals required.

Before each shrink step, record the window if it is shorter than the current best. The best is tracked as a tuple of (window_length, left_index, right_index) so you can extract the substring at the end with s[best_left : best_right + 1]. Update best only when the current window length is strictly less than the stored best length.

After shrinking as far as possible without breaking validity, advance right by one to expand again. This outer expand / inner shrink loop continues until right exhausts s. Each character is added to the window once by right and removed once by left, confirming the O(n) bound.

When s is very long but t is short, most characters of s are irrelevant — they are not in t at all and never contribute to satisfying requirements. The filtered string optimization creates a compressed version of s containing only characters that appear in t, paired with their original indices in s.

For example, if t is "ABC" and s is "AXBYCZ", the filtered list becomes [(0,'A'), (2,'B'), (4,'C'), (5,'Z')] — only positions holding A, B, C, or Z are kept. Wait, only characters in t's key set. The sliding window then operates over this filtered list instead of the full s, reducing the effective length dramatically when |t| << |s|.

The window boundaries in s are recovered using the original indices stored in the filtered list. The time complexity remains O(|s| + |t|) in the worst case but the constant factor improves significantly for inputs where s is sparse relative to t. This optimization is worth mentioning in interviews to show awareness of practical performance beyond big-O.

In Python, use collections.Counter for need and a defaultdict(int) for window. Set left = 0, formed = 0, required = len(need). Track best as (float("inf"), None, None). In the main loop, expand right: add s[right] to window; if s[right] in need and window[s[right]] == need[s[right]], increment formed. While formed == required: update best if right - left + 1 < best[0], then shrink left by decrementing window[s[left]] and checking if formed drops. Time is O(|s| + |t|), space is O(|s| + |t|) for the window and need maps.

In Java, use two HashMap<Character, Integer> objects for need and window. Parse t to build need with getOrDefault. The main loop mirrors Python: expand right, check and increment formed, inner while loop shrinks left. Use a length variable and two index variables (ansL, ansR) to track the best window instead of a tuple. Return ansL == -1 ? "" : s.substring(ansL, ansR + 1) at the end.

Both implementations share the same invariant: when formed == required the window is valid, and we greedily shrink left as far as possible before moving right again. The two maps together use O(|s| + |t|) space in the worst case — in practice, the window map holds at most |t| distinct characters since the window only grows useful when it captures t's characters.

Longest Substring Without Repeating Characters (LeetCode 3) is the entry-level sliding window problem — the window shrinks whenever a duplicate appears. Permutation in String (LeetCode 567) asks whether any window of s is a permutation of p, which is a fixed-size sliding window over character counts. Both build intuition for the variable-size window in LeetCode 76.

Substring with Concatenation of All Words (LeetCode 30) extends the pattern to multi-character tokens — instead of single characters, the window must contain all words from a list. Find All Anagrams in a String (LeetCode 438) finds all positions where a fixed-length window matches p's frequency map. These four problems together form the core sliding window family tested in senior interviews.

For further depth, Sliding Window Maximum (LeetCode 239) combines sliding window with a monotonic deque to track the max in O(n). Minimum Size Subarray Sum (LeetCode 209) uses a shrinkable window on sums rather than character counts. Mastering LeetCode 76's expand-shrink template unlocks all of these — the pattern of "expand until valid, shrink while valid, record best" appears in dozens of interview problems.