Sliding Window for Minimum Substring Problems

Recommended resources

The freely available resources this lesson will direct you to.

Hello! In our last session, we mastered the variable-size sliding window for "longest substring" problems. The core idea was to expand the window and, once it became invalid, shrink it just enough to restore its validity.

Today, we'll adapt that powerful pattern for a different goal: finding the shortest valid substring. This lesson focuses on applying a variable-size window to solve minimum-window problems where you need to include a specific set of characters. The core "expand-and-shrink" mechanic remains, but we'll strategically alter when and how we shrink the window. This subtle shift is the key to solving a whole new class of problems, including the classic LeetCode hard problem, "Minimum Window Substring."

The "Minimum Window" Pattern

In "longest substring" problems, we update our answer with every expansion and shrink the window only when a constraint is broken. The goal is to keep the window valid for as long as possible.

For "minimum window" problems, the logic is inverted:

Expand: Keep expanding the window by moving the right pointer until it just becomes valid (i.e., it satisfies the condition, such as containing all required characters).
Record and Shrink: Once the window is valid, we record this potential answer. Then, we try to find a smaller valid window by moving the left pointer inward. We shrink the window as much as possible, continuing as long as it remains valid.
Invalidate and Repeat: When shrinking finally makes the window invalid again, we stop shrinking and go back to step 1, expanding the right pointer to find the next valid window.

This cycle of "expand to validity, then shrink to the minimum" ensures we check every potential minimal substring efficiently.

The Canonical Problem: Minimum Window Substring

Let's ground this in a concrete problem, LeetCode 76.

The Problem: Given two strings, s and t, return the minimum window (contiguous substring) in s which contains all the characters of t, including duplicates. If there is no such window, return an empty string.

Example:

s = "ADOBECODEBANC"
t = "ABC"
Output: "BANC"

The substring "ADOBEC" is a valid window, but it's not the minimum. "BANC" is shorter and also contains 'A', 'B', and 'C'.

To solve this, we need a way to track two things:

The characters and their frequencies required by t.
The characters and their frequencies within our current sliding window in s.

A hash map is the perfect tool for this. We can use one map for the requirements from t and another for the state of our current window. However, comparing these two maps at every step would be inefficient. A more clever approach is to use a counter to track how many of the requirements have been met.

The following video from NeetCode provides an excellent walkthrough of this optimized logic. It introduces the idea of have and need counts to make our validity check an O(1) operation.

Minimum Window Substring - Airbnb Interview Question - Leetcode 76

This NeetCode video provides a full conceptual walkthrough and coding solution for the "Minimum Window Substring" problem.

First, watch the initial explanation to understand the problem and why a simple brute-force check is inefficient. Then, pay close attention to the optimized approach, where the concepts of have and need are introduced. This is the core optimization. Finally, observe the shrinking process, which demonstrates how the algorithm contracts a valid window from the left to find the absolute minimum. You can skim the final coding part as we will analyze a written implementation next.

A Structured Look at the Algorithm

The video gave us the intuition. Now, let's formalize the steps. The key is managing three pieces of information: the required character counts, the window's character counts, and a single counter variable that tells us if the window is valid.

The AlgoMonster article on this problem provides a very clear, structured breakdown.

76. Minimum Window Substring - In-Depth Explanation

This article from AlgoMonster dissects the sliding window solution for the Minimum Window Substring problem.

First, read the core idea and the formal steps under the Solution Approach section. This presents the logic in a structured way. Then, follow the Example Walkthrough carefully. It applies the steps to our running example, s = "ADOBECODEBANC" and t = "ABC", showing exactly how the pointers and counters change as the window first expands to ADOBEC, then shrinks and expands again to eventually find BANC.

As you saw, the process is systematic:

Initialization: Create a frequency map for t. Initialize left=0, a variable for minimum length (e.g., to infinity), and a start index for our result. We also need a counter for matched characters, let's call it matched_chars, initialized to 0. The total number of characters we need to match is simply len(t).
Expansion: Iterate through s with the right pointer. For each character c:
- Add c to the window's frequency map.
- If c is a required character (i.e., it's in t's map) AND its count in the window is now less than or equal to its required count, increment matched_chars.
Contraction: As soon as matched_chars == len(t), the window is valid. Now, we enter a while loop that runs as long as the window stays valid:
- Update our minimum length and result start index if the current window is smaller than the best we've seen so far.
- Get the character at the left pointer, left_char.
- Decrement its count in the window's frequency map.
- If left_char is a required character AND its count in the window has just dropped below its required count, decrement matched_chars. This is the point where the window becomes invalid.
- Increment the left pointer to shrink the window.

The outer for loop expands the window, and the inner while loop aggressively shrinks it, ensuring we always find the smallest possible valid window ending at the current right pointer.

The image below illustrates this search for a minimal window. The algorithm considers and discards larger valid windows (like steps 3 and 4) in favor of smaller ones (like step 6).

A visualization of the sliding window finding the smallest substring. The window expands until valid (steps 1-3), then shrinks from the left to find a smaller valid window (steps 4-6).

Implementation Details

Let's examine a clean Python implementation from the AlgoMonster article. It directly translates the logic we just discussed.

76. Minimum Window Substring - In-Depth Explanation

This resource provides the code and discusses common implementation errors.

Please read the Python solution. Pay special attention to these lines: if char in target_freq and window_freq[char] <= target_freq[char]: matched_chars += 1 This is the condition to increment our match counter during expansion. while matched_chars == len(t): This is the trigger to start the contraction phase. if left_char in target_freq and window_freq[left_char] < target_freq[left_char]: matched_chars -= 1 This is a key detail from a correction later in the article. The condition to decrement the match counter is when the window's count for a required character drops strictly below the target count. Finally, read the section Additional Pitfall. This highlights a crucial edge case: for a target like t = "AAB", you must match len(t) = 3 characters, not just the len(unique_chars) = 2 unique characters.

This implementation elegantly captures the expand-and-shrink logic for minimum window problems. Your background in solving LeetCode problems should help you appreciate the efficiency of this O(m+n) approach over a naive O(m² * n) one.

Conclusion

In this lesson, we adapted the variable-size sliding window pattern to solve "minimum window" problems. We saw that the strategy is different from "longest substring" problems: instead of shrinking on invalidity, we expand to validity and then shrink aggressively to find the shortest possible valid window.

Key Takeaways:

The minimum window pattern is: expand until valid, then shrink while still valid.
State management involves a frequency map for the target string (t) and one for the current window.
An efficient validity check is crucial. Using a counter for matched characters (e.g., matched_chars) that is updated during expansion and contraction allows for O(1) checks.
The contraction phase is key: once a valid window is found, you immediately try to shrink it from the left, updating your minimum result at each step, until the window is no longer valid.

In our next lesson, we'll explore another fundamental two-pointer pattern: using pointers that move from opposite ends of an array inwards. This technique is particularly effective for solving search and sum problems on sorted arrays.