Minimum Window Substring: The Hardest Sliding Window Problem

If there is one problem that proves you truly understand the sliding window pattern, it is Minimum Window Substring — LeetCode #76. This Hard-level problem appears consistently in interviews at Google, Meta, Amazon, and Microsoft. It is the problem interviewers reach for when they want to see if a candidate can handle the full complexity of sliding windows, not just the textbook version.

What makes this minimum window substring leetcode problem so demanding is that it combines every sliding window concept into a single challenge. You need a variable-size window, frequency counting with hash maps, a satisfaction condition that tracks multiple characters simultaneously, and the discipline to shrink the window optimally once the condition is met. Most candidates who can solve Medium sliding window problems hit a wall here.

This walkthrough breaks the problem down into its components, explains the approach step by step, and shows you exactly why each piece is necessary. By the end, you will have the complete toolkit for solving not just this problem, but every sliding window variant you encounter.

The problem statement is deceptively simple: given two strings s and t, find the minimum window in s that contains all characters of t, including duplicates. If no such window exists, return an empty string. For example, if s is "ADOBECODEBANC" and t is "ABC", the answer is "BANC" — the smallest substring of s that contains A, B, and C.

The critical detail that trips people up is the phrase "including duplicates." If t is "AAB", your window must contain at least two As and one B. A window with only one A does not qualify, no matter how small it is. This duplicate requirement is what forces you to use frequency counting rather than a simple set.

The brute force approach — checking every possible substring of s — runs in O(n squared) time at best, which is far too slow for the constraint of s up to 100,000 characters. You need a linear-time solution, and that is exactly what the sliding window with hash maps provides.

The optimal solution uses a sliding window with two hash maps and runs in O(n) time where n is the length of s. The core idea is elegant: expand the window to the right until it contains all required characters, then shrink it from the left to find the minimum valid window. Repeat this expand-shrink cycle across the entire string.

You maintain two frequency maps. The first, often called need, stores the frequency of each character in t — this never changes. The second, often called have, tracks the frequency of each character inside your current window. As you expand right, you increment counts in have. As you shrink left, you decrement them.

The key insight that makes this efficient is a counter variable, typically called formed, that tracks how many unique characters in t have their required frequency satisfied in the current window. When formed equals the number of unique characters in t, your window is valid and you can try shrinking it. This avoids the expensive step of comparing the entire frequency map on every iteration.

This minimum window sliding window technique is the same expand-then-shrink pattern used in simpler problems, but with the added complexity of tracking multiple character frequencies simultaneously.

The implementation has several moving parts, but each one serves a clear purpose. Start by building the need map from t — iterate through t and count the frequency of each character. Also record the number of unique characters in t, which we call required. Initialize have as an empty map and formed as zero.

Use two pointers, left and right, both starting at index zero. Expand right one step at a time. For each new character at position right, increment its count in have. If the count of that character in have now equals its count in need, increment formed by one. This means one more unique character has been fully satisfied.

Once formed equals required, your window is valid. Record the window if it is smaller than any previous valid window. Then try to shrink from the left: decrement the count of the character at left in have. If that count drops below what need requires, decrement formed. Move left forward. Keep shrinking as long as the window remains valid.

The time complexity is O(n) because each character is visited at most twice — once by right expanding and once by left shrinking. Space complexity is O(k) where k is the number of unique characters in s and t combined, typically bounded by the alphabet size.

Minimum Window Substring earns its Hard label not because any single concept is difficult, but because it demands you juggle multiple concepts simultaneously without dropping any. Two hash maps, a formed counter, a running minimum window, correct duplicate handling, and precise expand-shrink logic — each one is straightforward in isolation, but combining them under interview pressure is where candidates fail.

The most common mistake is re-checking the entire frequency map on every step to determine if the window is valid. This turns an O(n) solution into O(n times k) and often leads to time limit exceeded. The formed counter is the optimization that makes the approach work at scale, but many candidates do not think of it on their own.

Another frequent error is mishandling the shrink phase. Candidates either shrink too aggressively and miss valid windows, or they forget to shrink at all and return a window that is larger than necessary. The discipline of shrinking only while the window remains valid — and immediately recording the minimum — is the mechanical skill this hard sliding window problem tests.

Duplicate characters add a final layer of complexity. If t is "AABC", your have map must track that A needs a count of two, not just that A is present. Off-by-one errors in the frequency comparison are extremely common and difficult to debug under time pressure.

Before submitting your solution, walk through these edge cases that interviewers frequently test. Missing even one can turn an otherwise correct solution into a wrong answer.

When t is longer than s, no valid window can exist — return an empty string immediately. When t contains duplicate characters, your frequency map must reflect the exact count needed, not just the presence of each character. When all characters in s are the same and t is a single character, the minimum window is length one.

Another subtle case is when s and t are identical. The entire string is the minimum window. Also consider when t has characters not present in s at all — again, return empty immediately. Testing these cases during an interview demonstrates thoroughness and builds interviewer confidence in your solution.

Minimum Window Substring is not just a problem — it is a masterclass in the complete sliding window toolkit. The expand-check-shrink cycle you learn here applies directly to Longest Substring Without Repeating Characters (#3), Permutation in String (#567), Substring with Concatenation of All Words (#30), and dozens of other window-based problems. If you can solve #76, every other sliding window problem becomes easier.

The frequency counting pattern — maintaining a have map and a need map — extends beyond sliding windows into problems involving anagrams, permutations, and character matching. The formed counter optimization teaches you to think about incremental state tracking instead of recomputing from scratch, a principle that applies across all of algorithm design.

This is the problem that interviewers use to separate candidates who have memorized a template from those who truly understand why each piece of the sliding window pattern exists. Practice it until you can explain every variable, every condition, and every edge case. Review it with YeetCode flashcards to build the recall that makes this pattern automatic under interview pressure.