Minimum Window Substring Algorithm

Welcome back! In our last lesson, we introduced the powerful technique of tracking character frequencies and a "satisfaction count" within a sliding window. You saw how this allows us to efficiently check if a window meets complex criteria, like being a permutation of another string.

Today, we will formalize and master a crucial pattern built on that foundation: finding the minimum valid substring window. While you've already had a glimpse of the "Minimum Window Substring" problem, this lesson will focus specifically on the elegant expand-and-contract logic that allows us to find the shortest possible substring that satisfies a set of requirements. This is a common and important interview pattern, and understanding its mechanics is key to solving a wide range of problems.

The Minimum Window Substring Problem

Let's begin by clearly defining the problem we'll be working with.

Given two strings, s and t, find the minimum contiguous substring of s which contains all the characters of t. The frequency of characters in the substring must be greater than or equal to their frequency in t.

The image below illustrates this. We have a long string s and a shorter string t. The goal is to find the smallest possible "window" in s that contains all the characters from t. Notice that t can have duplicate characters, and the window must contain at least that many duplicates.

The brute-force approach—checking every single substring in s—would be far too slow, likely $O(m^2\cdot n)$ or worse, where $m$ is the length of s and $n$ is the length of `t). A sliding window offers a much more efficient path.

The Expand and Contract Rhythm

The core idea of the algorithm is a dynamic two-phase process:

1. Expand: We grow the window by moving its right pointer. We keep expanding until the window contains all the required characters from t. We'll call such a window "valid."
2. Contract: Once we have a valid window, we've found a potential answer. But is it the minimum? To find out, we shrink the window from the left, moving the left pointer inward. We keep shrinking as long as the window remains valid. Each time we shrink, we have a new, smaller, valid window, which might be our new best answer.

We stop shrinking the moment the window becomes invalid (i.e., it no longer contains all the required characters). At this point, the cycle repeats: we go back to expanding the right side to find the next valid window.

This image shows the process on a different example. The window first expands until it becomes valid ("abdec" contains a, b, and c). Then, it starts shrinking from the left.

The 'Have' vs. 'Need' Mental Model

In the last lesson, we introduced the concept of a satisfaction count. A very intuitive way to manage this for the minimum window problem is to track what you have versus what you need.

• need: The number of unique characters in t whose frequency requirements we must satisfy.
• have: The number of unique characters in our current window that have met or exceeded their required frequency from t.

The window is valid when have === need. This simple check is the trigger to switch from expanding to contracting.

The following video from NeetCode provides an excellent walkthrough of this logic. It starts by showing why a naive check is inefficient and then builds up the have/need optimization.

The process described in the video can be summarized with the following logic structure:

This diagram shows the cycle: expand until valid (C), then enter the inner loop of updating the result (D) and contracting (E) until the window is no longer valid (F), at which point you go back to expanding.

A Detailed Walkthrough and Implementation

Now that you have the intuition, let's look at a detailed breakdown and a TypeScript implementation. The resource from Algo.monster provides a clear, step-by-step guide that formalizes the approach.

The TypeScript implementation in that resource uses matchedChars and targetLength (total characters) instead of have and need (unique characters), but the underlying principle is the same. Both are valid ways to implement the satisfaction count. The have/need approach is often slightly simpler when dealing with duplicates, as you only increment have once per character type.

Common Pitfalls

When implementing this pattern, several subtle bugs can arise. Being aware of them is crucial, especially in an interview setting.

Conclusion

You have now dissected one of the most versatile sliding window patterns. The ability to find a minimum window that satisfies complex criteria is a significant step up from basic fixed-size or simple variable-size windows.

Key Takeaways:

• Expand-Contract Cycle: The algorithm for minimum-length window problems follows a rhythm: expand the window with the right pointer until it's valid, then contract it from the left until it's invalid, updating your best result along the way.
• Nested Loop Structure: This logic is typically implemented with a for loop for the right pointer and a nested while loop for the left pointer. The while loop only executes when the window is valid.
• Efficient Validity Check: Using frequency maps and a satisfaction counter (like have/need or matchedChars) allows the validity of the window to be checked in $O(1)$ time at each step.
• Linear Time Complexity: Because each character in the input string s is visited at most twice (once by the right pointer and once by the left), the overall time complexity is $O(m+n)$, where $m$ and $n$ are the lengths of the strings s and t.

In our next lesson, we'll explore a different application of the two-pointers technique: partitioning an array. Instead of finding a contiguous subarray, we'll use pointers to rearrange elements within an array based on a specific condition. This will further broaden your toolkit for array manipulation problems.