Minimum Window Substring: Sliding Window & HashMap

1. Understanding the Problem

The task is to find the smallest contiguous substring within a larger string s that contains all the characters of another string t. Importantly, this includes handling duplicate characters. If t is "AAB", the substring in s must contain at least two 'A's and one 'B'.

Let's look at a canonical example:

• s = "ADOBECODEBANC"
• t = "ABC"

The smallest substring in s containing 'A', 'B', and 'C' is "BANC". Notice that the order doesn't matter, and there can be other characters in the window (like 'N'). The challenge is to find this minimal window efficiently.

2. The Brute-Force Approach: A Starting Point

As we always do, let's start with the most straightforward, intuitive solution. The problem asks for the "smallest substring," so a natural first thought is to examine all possible substrings of s.

The algorithm would look like this:

1. Generate every single substring of s. This can be done with nested loops, where the outer loop sets the start index i and the inner loop sets the end index j.
2. For each generated substring, we must verify if it's a "valid" window—that is, if it contains all characters from t with the required frequencies.
3. To perform this check, we can use two HashMaps: one to store the frequency of characters in t, and another to store the frequency of characters in the current substring from s. We then compare the maps.
4. If a substring is valid, we compare its length to the minimum length found so far and update it if we've found a new, smaller valid window.

This method guarantees a correct answer but is highly inefficient. Generating all substrings and repeatedly checking their validity involves a lot of redundant computation.

3. The Optimal Solution: A Two-Pointer Sliding Window

The brute-force approach is slow because it re-scans and re-computes frequencies for overlapping substrings. The sliding window technique elegantly solves this by maintaining a single, dynamic window and adjusting its boundaries.

The core strategy is:

1. Expand the window by moving the right pointer. Keep adding characters to the window until it becomes valid (i.e., contains all required characters from t).
2. Once the window is valid, shrink it from the left by moving the left pointer. We do this to find the smallest possible valid window. We continue shrinking as long as the window remains valid.
3. When shrinking makes the window invalid, we go back to step 1 and expand again.

To implement this efficiently, we need a few key components:

• A HashMap (targetFreq) to store the character frequencies of string t.
• A second HashMap (windowFreq) to store the character frequencies within our current sliding window.
• Two pointers, left and right, initialized to 0.
• A counter mechanism to tell us when our window is valid. A great way to do this is to have a required variable (the number of unique characters in t) and a formed variable (the number of unique characters in our window that meet or exceed the required frequency). The window is valid when formed == required.

Let's walk through the logic:

// Conceptual Variables
Map<Character, Integer> targetFreq; // Pre-calculated from string t
Map<Character, Integer> windowFreq; // For the current window s[left..right]

int required = targetFreq.size();
int formed = 0;

int left = 0;
int minLength = Integer.MAX_VALUE;
int resultStart = 0;

for (int right = 0; right < s.length(); right++) {
    // 1. EXPAND the window to the right
    char charRight = s.charAt(right);
    windowFreq.put(charRight, windowFreq.getOrDefault(charRight, 0) + 1);

    // 2. CHECK if adding charRight helped us form a required character
    if (targetFreq.containsKey(charRight) && 
        windowFreq.get(charRight).intValue() == targetFreq.get(charRight).intValue()) {
        formed++;
    }

    // 3. SHRINK the window from the left once it's valid
    while (left <= right && formed == required) {
        // A valid window is found. Update our result.
        if (right - left + 1 < minLength) {
            minLength = right - left + 1;
            resultStart = left;
        }

        // Try to shrink further
        char charLeft = s.charAt(left);
        windowFreq.put(charLeft, windowFreq.get(charLeft) - 1);

        // 4. CHECK if removing charLeft broke the validity
        if (targetFreq.containsKey(charLeft) && 
            windowFreq.get(charLeft) < targetFreq.get(charLeft)) {
            formed--;
        }

        left++; // Move the left pointer
    }
}

This interplay between expanding the window to satisfy a condition and contracting it to optimize the result is the heart of the sliding window pattern for this type of problem.

The image below from the takeuforward tutorial illustrates this process of expanding and then shrinking.

Now, let's study the complete implementation and the detailed algorithm steps.

To see this logic animated, watching a visual dry run can be incredibly helpful. Striver's video provides exactly that.

Conclusion

In this lesson, we tackled the "Minimum Window Substring" problem, a significant step up in complexity within the sliding window paradigm. By following our structured approach, we moved from an inefficient brute-force method to a linear-time optimal solution.

Key Takeaways:

• Problem: Find the smallest substring in s that contains all characters (including duplicates) from t.
• Pattern: The problem is solved using a variable-size sliding window with a distinct "expand-then-contract" rhythm.
• Expansion: The window grows by moving the right pointer until it becomes valid (contains all required characters).
• Contraction: Once valid, the window shrinks from the left to find the smallest possible size while maintaining validity.
• Data Structures: Two HashMaps are used to efficiently track the required character frequencies (t) and the current window's frequencies (s).
• Complexity: The optimal sliding window solution achieves a time complexity of O(N+M) and space complexity of O(M), making it highly efficient for interviews.

In our next lesson, we will apply the sliding window technique to another problem: counting the number of substrings with at most K distinct characters. This will reinforce your understanding of the pattern while introducing a slightly different constraint to work with.