Minimum Window Substring Problem Solution

The Minimum Window Substring problem requires finding the smallest contiguous substring in a source string that contains all characters of a target string. This classic sliding window pattern efficiently solves the problem in linear time by maintaining character frequency counts and expanding/shrinking a dynamic window.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Can the input strings contain duplicate characters? Should we account for frequency of characters?
2. What is the expected time complexity target for the solution? Are we aiming for O(n) or can we accept O(n log n)?
3. Do we need to preserve the original input strings, or can we modify them in-place?
4. What is the maximum length of the input strings? This will help determine if we can use O(n) space.
5. Should we return the actual substring or just the start index and length?

Restatement of the pattern: The Minimum Window Substring problem asks us to find the smallest contiguous substring in a given string (the "window") that contains all characters of another string (the "pattern") with at least the same frequency as in the pattern.

Signal words and constraint shape:

• "minimum window" or "smallest substring"
• "contains all characters of pattern"
• "at least the same frequency"
• Input string and pattern string with potentially different lengths
• Requires maintaining character counts for comparison

Assumptions made:

• Both input strings contain only ASCII characters (or at least a fixed character set)
• The pattern string is not empty
• We're looking for a contiguous substring in the main string that satisfies the character frequency requirements

Scenario fit: This pattern is best suited for static scenarios where we have complete input data upfront. It's not ideal for streaming data where the pattern might change dynamically or where we need to maintain a sliding window over time. For streaming scenarios, we'd likely want a different approach like maintaining a dynamic frequency map with window expansion/shrinkage.

The pattern represents a classic sliding window technique where we maintain character frequency counts to efficiently find the optimal window bounds.

2. When to Use This Pattern

Signal words and constraint shapes:

• "minimum window" or "smallest substring"
• "contains all characters of another string"
• "substring with specific character frequencies"
• Input is typically a string or array where we're looking for a minimal contiguous substructure
• Often involves character frequency matching or sliding window constraints

Why this pattern fits better than alternatives: This pattern is ideal when we need to find the smallest contiguous substructure that satisfies a specific constraint. Unlike brute force approaches that check every substring (O(n³)), sliding window techniques can achieve O(n) time complexity by maintaining a valid window and efficiently expanding/shrinking it. Compared to two-pointer approaches, this pattern specifically leverages the constraint that we're looking for a "minimum" valid window rather than just any valid window.

Conditions where variations apply:

• When we're looking for a fixed-size window instead of minimum size, use fixed-size sliding window
• When we're counting occurrences rather than matching character frequencies, use frequency-based approaches
• When the constraint is not about character inclusion but about ordering or specific values, consider other pattern matching approaches

Core insight that makes this pattern work: The key insight is that we can maintain a "valid window" where all required characters are present in sufficient quantities, and by sliding the window boundaries, we can find the minimum valid window. The sliding window technique works because once we have a valid window, expanding it only makes it larger (and potentially invalid), while shrinking it from the left maintains the constraint until we find the minimal valid window.

The pattern is particularly effective when:

1. The constraint can be checked in O(1) time for a window
2. Valid windows form a contiguous region that can be efficiently maintained
3. We're looking for a minimal or maximal contiguous substructure with specific properties

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every possible substring and see if it contains all characters from the target string. But that's O(n³) because for each starting position, I'd need to check all ending positions and validate the character counts - that's way too slow.

Let me think about how to optimize this. I notice that if I use a sliding window technique, I can maintain a valid window and expand/contract it efficiently. If I keep track of character frequencies in both the target and current window, I can maintain an invariant that the current window contains all required characters.

I notice that if I maintain a sliding window with two pointers and keep expanding the right pointer until I have all required characters, then I can contract from the left while maintaining that invariant. This reduces it to O(n) time complexity by ensuring each element is visited at most twice.

The key insight is that I can use a frequency map to track how many of each character I need vs. how many I have, and maintain a "valid" counter that tells me when my window contains all required characters.

Brute-force approach and why it is not ideal:

The brute force approach would involve checking every possible substring of the input string and verifying if it contains all characters from the target string with sufficient frequency. For each starting position i, we'd iterate through all ending positions j and check if substring s[i:j+1] contains all required characters.

This approach is not ideal because:

• Time complexity is O(n³) - O(n²) substrings, each checked in O(n) time
• It's highly redundant - we're recalculating character counts repeatedly
• We don't leverage the fact that once we have a valid window, we can try to shrink it

Improved approach and the key optimization:

The key optimization is using a sliding window with two pointers. We maintain a window that expands to include new characters until we have all required characters, then contract from the left while maintaining validity. The crucial insight is that we can use character frequency maps to efficiently track when our window becomes valid and stays valid.

Final approach with step-by-step reasoning:

1. Use two pointers (left and right) to maintain a sliding window
2. Expand the window by moving right pointer until we have all required characters in our current window
3. Once valid, try to contract the window from left while maintaining validity - this gives us a candidate minimum window
4. Continue expanding and contracting until we've processed the entire string
5. Keep track of the smallest valid window found so far

The important invariants that must hold:

• The window always contains all required characters from the target string
• We only contract when we have a valid window (contains all required chars)
• We track the minimum valid window size throughout the process

Key insight: Each character in the input string is processed at most twice (once when expanding, once when contracting), making it O(n) time complexity.

4. Data Structure Choice

For the Minimum Window Substring problem, I'll use a combination of data structures to achieve optimal performance:

Primary Data Structures:

1. HashMap<Character, Integer> - Used to store the frequency count of characters in the target string t. This allows O(1) lookup and update operations when checking character frequencies.

2. HashMap<Character, Integer> - Used to maintain the current window's character frequency count from string s. This helps track which characters are currently in our sliding window and their counts.

3. Two Pointers (integers) - Used to maintain the sliding window bounds (left and right). These are simple integers that can be efficiently moved.

Why Each Data Structure Is Needed:

The HashMap for target character frequencies is essential because we need to know exactly what characters and how many of each we must have in our window to consider it valid. The second HashMap is crucial for maintaining the current window state and efficiently checking whether we've met the required character counts.

The two pointers are fundamental to the sliding window technique - they allow us to expand and contract our search space efficiently without reprocessing elements multiple times.

Time and Space Impact:

• Time Complexity: O(|s| + |t|) where |s| and |t| are the lengths of the strings
• Space Complexity: O(k) where k is the number of unique characters in t (for the hash maps)

Helper Structures:

I'll use a simple integer counter requiredChars to track how many unique characters from t we still need to satisfy in our current window. This avoids having to iterate through the entire frequency map on every window update.

This combination provides a clean, efficient way to implement the sliding window algorithm while maintaining readable code structure. The hash maps provide constant-time access to character counts, which is crucial for the O(n) time complexity of this approach.

5. Algorithm Walkthrough

Let me trace through the sliding window approach with the example s = "ADOBECODEBANC", t = "ABC".

Step 1: Initialize variables

• need map: {A:1, B:1, C:1}
• window map: empty
• left = 0, right = 0
• valid = 0 (number of characters that meet requirement)
• start = 0, len = Integer.MAX_VALUE (to track minimum window)

Step 2: Expand window by moving right

• right = 0: char = 'A'
  • 'A' is in need map, window[A] becomes 1
  • Since window[A] == need[A], valid increments to 1
• right = 1: char = 'D'
  • 'D' not in need, just expand window
• right = 2: char = 'O'
  • 'O' not in need, just expand window
• right = 3: char = 'B'
  • 'B' is in need, window[B] becomes 1
  • Since window[B] == need[B], valid increments to 2

Step 3: Contract window when valid = 3

• right = 4: char = 'E'
  • 'E' not in need, just expand window
• right = 5: char = 'C'
  • 'C' is in need, window[C] becomes 1
  • Since window[C] == need[C], valid increments to 3

Now valid = 3, so we have a valid window [0,5] = "ADOBEC"

• Update min window: start=0, len=6
• Contract window by moving left

Step 4: Contract window

• left = 0: char = 'A'
  • 'A' is in need, window[A] becomes 0
  • Since window[A] < need[A], valid decrements to 2
  • Window [1,5] = "DOBEC" is not valid anymore

Step 5: Continue expanding and contracting

• right = 6: char = 'O'
  • Not in need, expand window
• right = 7: char = 'D'
  • Not in need, expand window
• right = 8: char = 'E'
  • Not in need, expand window
• right = 9: char = 'B'
  • In need, window[B] becomes 2
  • Since window[B] > need[B], no change to valid

Step 6: Continue expanding until we find another valid window

• right = 10: char = 'A'
  • In need, window[A] becomes 1
  • Since window[A] == need[A], valid increments to 3 again
• Now we have valid window [9,10] = "BA" but this is not minimal
• Continue expanding...

Step 7: Find final window [9,12] = "BANC"

• right = 11: char = 'N'
  • Not in need, expand window
• right = 12: char = 'C'
  • In need, window[C] becomes 2
  • Since window[C] > need[C], no change to valid

Step 8: Contract window from left side

• left = 9: char = 'B'
  • In need, window[B] becomes 1
  • Since window[B] == need[B], valid stays at 3
• left = 10: char = 'A'
  • In need, window[A] becomes 0
  • Since window[A] < need[A], valid decrements to 2

Step 9: Continue until we find minimal window [1,5] = "DOBEC"

• This is not the answer since we want minimum window that contains all chars of t

Final Step: The algorithm continues until right reaches end of string

• Eventually finds window [9,12] = "BANC" with length 4
• This is our answer since it's the minimal window containing all characters of "ABC"

The algorithm correctly identifies that we need to maintain a sliding window where the count of each character in t is satisfied, and keeps track of the minimal such window found so far.

6. Java Solution

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        // Handle edge cases
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }
        
        // Count characters in target string t
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        
        // Sliding window variables
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;
        int requiredChars = need.size(); // Number of unique characters needed
        int formedChars = 0; // Number of unique characters in window that match need count
        
        // Track character counts in current window
        Map<Character, Integer> window = new HashMap<>();
        
        // Expand the sliding window by moving right pointer
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
            
            // Check if this character matches the required count in t
            if (need.containsKey(rightChar) && 
                window.get(rightChar).intValue() == need.get(rightChar).intValue()) {
                formedChars++;
            }
            
            // Try to contract window from left while maintaining validity
            while (left <= right && formedChars == requiredChars) {
                char leftChar = s.charAt(left);
                
                // Update minimum window if current window is smaller
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                
                // Remove leftmost character from window
                window.put(leftChar, window.get(leftChar) - 1);
                if (need.containsKey(leftChar) && 
                    window.get(leftChar).intValue() < need.get(leftChar).intValue()) {
                    formedChars--;
                }
                
                left++;
            }
            
            right++;
        }
        
        // Return minimum window substring or empty string if none found
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

This solution implements the sliding window technique to find the minimum window substring. The approach uses two pointers (left and right) to maintain a dynamic window that expands and contracts based on whether all characters from string t are included in the current window. The key insight is that we only need to track character frequencies rather than actually matching substrings, which makes the solution efficient and clean.

7. Complexity Analysis

Time Complexity: O(|s| + |t|)

The algorithm uses a sliding window approach with two pointers that traverse the string s exactly once. Each character in s is visited at most twice (once by the right pointer, once by the left pointer), making the time complexity linear in the size of the input string.

Space Complexity: O(|t|)

The space complexity is determined by the HashMap used to store the character frequencies of string t. In the worst case, all characters in t are distinct, requiring space proportional to the length of t. Additionally, the auxiliary space for the result variables is constant.

Why these bounds are correct:

The linear time complexity arises because each character in the input string s is processed at most twice - once when expanding the window (moving right pointer), and once when contracting it (moving left pointer). The character frequency map for string t is bounded by its length, which is the maximum number of distinct characters we might need to track.

Optimality:

This solution is optimal for the minimum window substring problem. Since we must examine each character in the input string at least once to determine if it contributes to a valid window, O(|s| + |t|) is the best possible time complexity. The space complexity is also optimal since we must store information about all unique characters in the target string t to validate window inclusion.

The solution achieves the theoretical lower bound for this problem, making it near-optimal in both time and space complexity.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty s or t: If either string is empty, the result should be an empty string. Handle this early with boundary checks.
• Single character strings: When s is "a" and t is "a", the result should be "a".

Duplicate Values and Repeated States

• Duplicate characters in t: If t = "aab" and s = "aabb", the window must contain at least two 'a' characters and one 'b'.
• Multiple valid windows: When multiple substrings satisfy the condition, return the minimum-length one. For example, s = "ADOBECODEBANC", t = "ABC" has valid windows like "ADOBEC" and "BANC", but the minimum is "BANC".

Boundary Conditions

• t longer than s: If t is longer than s, return an empty string since no valid window can exist.
• t contains characters not in s: If t = "ab" and s = "ac", no valid window exists, so return an empty string.
• Exact match: If s exactly matches t, return s.

Common Implementation Mistakes

• Incorrect character counting: Not properly tracking required character counts in the sliding window, leading to false negatives.
• Incorrect window expansion/shrinking: Failing to shrink the window only when all required characters are present, or shrinking too aggressively.
• Not handling character frequency mismatches: Assuming that if a character is in t, it must appear the same number of times in the window.
• Off-by-one errors: Mismanaging indices when updating minStart and minLength.
• Not resetting window state: Failing to reset character counts or required character count when starting a new window.

// Example edge case handling:
if (s == null || t == null || s.length() == 0 || t.length() == 0) {
    return "";
}
if (t.length() > s.length()) {
    return "";
}

9. Alternative Approaches

There are several alternative approaches to solving the Minimum Window Substring problem, each with different trade-offs:

1. Brute Force with Sliding Window Instead of using a hashmap to track character frequencies, we could use nested loops to check every possible window. For each starting position, we expand the window until all required characters are included, then shrink from left while maintaining validity. This approach has O(n³) time complexity due to repeated character counting and is inefficient for large inputs.

2. Two Pointers with Character Count Array For problems involving only lowercase English letters, we could use a fixed-size array of size 26 instead of a HashMap to track character frequencies. This reduces constant factors and improves cache locality, but it's only applicable when the character set is known and limited.

3. Binary Search on Window Size We could binary search on the window size, checking for each candidate size whether a valid window exists. This approach requires O(n) verification for each binary search step, resulting in O(n log n) overall time complexity. It's less intuitive and more complex to implement than the standard sliding window approach.

4. Hash Map with Character Frequency Matching Instead of maintaining a separate "match" counter, we could compare character frequency maps directly at each window. This approach is more readable but has higher constant factors due to map comparisons and potentially more memory usage.

The chosen sliding window with hashmap approach is preferred because it provides optimal O(n) time complexity, clear logic flow, and handles arbitrary character sets efficiently. The alternatives either have worse time complexity or introduce unnecessary implementation complexity for the general case.

The standard sliding window with hashmap is the most practical and efficient solution for this problem's constraints.

10. Test Cases

public class MinimumWindowSubstringTestCases {
    
    // Basic test case: exact match
    @Test
    public void testBasicCase() {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        assertEquals("BANC", new Solution().minWindow(s, t));
    }
    
    // Edge case: empty string
    @Test
    public void testEmptyString() {
        String s = "";
        String t = "A";
        assertEquals("", new Solution().minWindow(s, t));
    }
    
    // Edge case: s contains all characters of t but in wrong order
    @Test
    public void testWrongOrder() {
        String s = "AABBBBCC";
        String t = "ABC";
        assertEquals("ABBBBC", new Solution().minWindow(s, t));
    }
    
    // Edge case: duplicate characters in t
    @Test
    public void testDuplicateCharsInT() {
        String s = "AABAACAA";
        String t = "AAB";
        assertEquals("AABA", new Solution().minWindow(s, t));
    }
    
    // Edge case: t is longer than s
    @Test
    public void testTLongerThanS() {
        String s = "AB";
        String t = "ABC";
        assertEquals("", new Solution().minWindow(s, t));
    }
    
    // Edge case: s equals t
    @Test
    public void testSEqualsT() {
        String s = "ABC";
        String t = "ABC";
        assertEquals("ABC", new Solution().minWindow(s, t));
    }
    
    // Edge case: multiple valid windows - should return the smallest
    @Test
    public void testMultipleValidWindows() {
        String s = "ADOBECODEBANC";
        String t = "AABC";
        assertEquals("BANC", new Solution().minWindow(s, t));
    }
}

11. Final Summary

The core idea is to find the minimum substring in s that contains all characters of t with their required frequencies using a sliding window technique. This solution works efficiently by maintaining a dynamic window that expands to include new characters and contracts when all required characters are present, ensuring optimal performance through careful tracking of character counts and window validity.

The solution is efficient because it uses a two-pointer sliding window approach with O(n + m) time complexity where n is the length of s and m is the length of t, avoiding redundant character checks by maintaining a valid window invariant. The use of HashMaps for character frequency tracking and a simple counter to track window completeness makes the implementation clean and maintainable while achieving optimal runtime characteristics for this constraint satisfaction problem.