Minimum Window Substring Problem Solution

The minimum window substring problem requires finding the smallest substring in a given string that contains all characters of another string. This classic sliding window problem demonstrates efficient string manipulation and frequency counting techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input strings contain special characters or only alphanumeric characters?
2. Are we guaranteed that the t string will always be a substring of s, or should we handle cases where it's not possible?
3. Should we return the actual substring or just its start and end indices?
4. Can we modify the input strings, or do we need to preserve them?
5. What's the expected time complexity for the follow-up? O(n) or O(n log n) is preferred.

Restatement in my own words: Given two strings s and t, we need to find the minimum contiguous substring in s that contains all characters of t with their respective frequencies. The result should be the smallest window in s that includes every character from t at least as many times as they appear in t.

Clarification of inputs, outputs, and constraints:

• Input: Two strings s (source) and t (target pattern)
• Output: The minimum window substring of s that contains all characters from t
• Constraints:
  • 1 <= s.length, t.length <= 10^5
  • Both strings contain only uppercase and lowercase English letters
• Assumption: If no valid window exists, we return an empty string

Key data shape and structure:

• The problem involves character frequency counting and sliding window technique
• We're looking for a contiguous substring in s that satisfies character frequency requirements from t
• The solution space is bounded by the length of string s

The core challenge lies in efficiently tracking character frequencies while maintaining a sliding window that dynamically expands and contracts to find the optimal solution.

2. Pattern Recognition

The problem exhibits the sliding window pattern with a specific constraint on substring coverage.

Key signals in the wording:

• "minimum window" - indicates we're looking for an optimal substring of a specific size or content
• "contains all characters of t" - signals we need to maintain coverage of a specific set of elements
• "substring" - suggests we're looking at contiguous subarrays/strings with specific properties

Why this fits the sliding window pattern: The problem asks us to find the smallest contiguous substring in s that contains all characters from string t with their required frequencies. This is a classic sliding window problem where:

1. We have a variable-size window that expands and contracts
2. The window must maintain a specific property (contain all characters of t)
3. We're optimizing for the minimal size that satisfies this constraint

Core insight: The key insight is that we can use a two-pointer approach with a sliding window to efficiently find the minimum valid substring. We expand the right pointer to include more characters until we have a valid window, then contract from the left to find the minimal valid window.

This pattern is characterized by:

• Variable-size sliding window
• Need to maintain a "valid" state (contains all required characters)
• Optimization for minimal window size
• Two pointers moving in the same direction (both right, with left potentially catching up)

The problem is fundamentally about finding a minimal contiguous subsequence that satisfies a coverage constraint, making it a perfect fit for the sliding window technique.

3. Approach Evolution

My first instinct is to use a sliding window approach because this problem asks us to find the "minimum" substring that contains all characters of another string, which naturally suggests we should expand and contract a window to find the optimal solution. But let me think about how to implement this efficiently.

If I were to use a brute force approach, I'd check every possible substring and verify if it contains all characters from the target string. That would be O(n³) time complexity - checking each substring takes O(n²) and validating it takes O(n). That's clearly not acceptable for large inputs.

Let me think about how to optimize this. I notice that if I maintain a sliding window that expands to include new characters and contracts when all required characters are present, I can reduce it to O(n) time. The key insight is that once I have a valid window containing all characters, I can try to shrink it from the left while maintaining validity.

The approach is:

1. Use two pointers (left and right) to maintain a sliding window
2. Expand the right pointer until all required characters are included in the window
3. Once we have a valid window, try to shrink it from the left while maintaining validity
4. Keep track of the minimum valid window found so far

The invariant I need to maintain is that at any point, my sliding window contains all characters from the target string with their required frequencies. When I find a valid window, I can try to contract it from the left while still maintaining that property.

This approach is optimal because:

• Each element is visited at most twice (once by right pointer, once by left pointer)
• We never revisit elements once they're processed
• The window expansion and contraction is handled efficiently with character counting

The key optimization here is avoiding redundant checks by maintaining the window state and only expanding when necessary, rather than checking every substring. This reduces our complexity from O(n³) to O(n).

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 for character frequencies.

2. HashMap<Character, Integer> - Used to maintain the sliding window's character frequency count. This tracks how many of each character we currently have in our window.

3. Integer variables - Track the minimum window bounds (start index, length) and counters for matching characters.

Why These Choices:

The HashMap approach is essential because:

• It provides O(1) average time complexity for character frequency updates and lookups
• It naturally handles variable-length windows without requiring fixed-size arrays
• It allows us to efficiently track which characters are fully matched in our window

Space Impact:

• Space complexity is O(k) where k is the number of unique characters in string t
• In worst case (all unique characters), this becomes O(|t|) for the frequency map
• The sliding window frequency map is at most O(|s|) but typically much smaller

Helper Structures:

• We don't need any additional helper data structures beyond the two HashMaps
• Using primitive variables for tracking window bounds keeps space minimal and access fast

This combination provides the perfect balance between time efficiency (O(1) operations) and space usage for this sliding window problem.

5. Algorithm Walkthrough

Let me trace through the algorithm 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 frequency requirements)
• start = 0, len = Integer.MAX_VALUE (to track minimum window)

Step 2: Expand window by moving right

• right = 0: c = 'A'
  • window becomes {A:1}
  • need has 'A', so valid increments to 1
  • Window contains {A:1}, valid count = 1

Step 3: Continue expanding

• right = 1: c = 'D'
  • window becomes {A:1, D:1}
  • 'D' not in need, so no change to valid
• right = 2: c = 'O'
  • window becomes {A:1, D:1, O:1}
  • 'O' not in need, so no change to valid
• right = 3: c = 'B'
  • window becomes {A:1, D:1, O:1, B:1}
  • 'B' in need, so valid increments to 2
• right = 4: c = 'E'
  • window becomes {A:1, D:1, O:1, B:1, E:1}
  • 'E' not in need, so no change to valid
• right = 5: c = 'C'
  • window becomes {A:1, D:1, O:1, B:1, E:1, C:1}
  • 'C' in need, so valid increments to 3

Step 4: Window is valid (contains all characters from t)

• Now we can try to shrink window from left
• left = 0: c = 'A'
  • window becomes {A:0, D:1, O:1, B:1, E:1, C:1}
  • window['A'] = 0, so valid decrements to 2
  • Window no longer valid, so we stop shrinking

Step 5: Continue expanding window

• right = 6: c = 'O'
  • window becomes {A:0, D:1, O:2, B:1, E:1, C:1}
  • 'O' not in need, so no change to valid
• right = 7: c = 'D'
  • window becomes {A:0, D:2, O:2, B:1, E:1, C:1}
  • 'D' not in need, so no change to valid
• right = 8: c = 'E'
  • window becomes {A:0, D:2, O:2, B:1, E:2, C:1}
  • 'E' not in need, so no change to valid
• right = 9: c = 'B'
  • window becomes {A:0, D:2, O:2, B:2, E:2, C:1}
  • 'B' in need, but window['B'] = 2 > need['B'] = 1, so no change to valid
• right = 10: c = 'A'
  • window becomes {A:1, D:2, O:2, B:2, E:2, C:1}
  • 'A' in need, but window['A'] = 1 = need['A'] = 1, so valid increments to 3
• right = 11: c = 'N'
  • window becomes {A:1, D:2, O:2, B:2, E:2, C:1, N:1}
  • 'N' not in need, so no change to valid
• right = 12: c = 'C'
  • window becomes {A:1, D:2, O:2, B:2, E:2, C:2, N:1}
  • 'C' in need, but window['C'] = 2 > need['C'] = 1, so no change to valid

Step 6: Check for minimum window

• At right = 10, we have valid window {A:1, D:2, O:2, B:2, E:2, C:1} (substring "ADOBEC")
• Length = 6, len is updated to 6, start becomes 0
• Continue expanding and shrinking as needed

Step 7: Final result

• The algorithm continues until right reaches end of string
• When we find the minimum valid window, it will be "BANC" with length 4
• start = 9, len = 4 → return substring from index 9 to 12

The key insight is that we expand the window until we have all required characters, then contract it from left while maintaining validity to find the minimal valid window.

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 frequency of characters in 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 current window with sufficient count
        
        // Map to store character frequencies 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);
            
            // Add character to window
            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 removing this character breaks the required count, decrement formedChars
                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 uses the sliding window technique with two pointers to efficiently find the minimum window substring. The key insight is to maintain a window that contains all characters of string t with their required frequencies, and dynamically adjust the window size to find the optimal solution.

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 and 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 character frequencies from string t. In the worst case, all characters in t are distinct, requiring space proportional to the length of t. Additionally, we use a few integer variables for tracking window state, which contribute constant space.

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 size is bounded by the unique characters in t, which is at most |t|.

Optimality:

This solution achieves optimal time complexity for this problem since we must examine each character in the input at least once to determine if it contributes to forming a valid window. The space complexity is also optimal as we must store the character frequencies from t to determine what constitutes a valid window.

The solution is near-optimal in that it achieves the theoretical lower bound for both time and space complexity for this specific problem variant.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty s or t: If either string is empty, the result should be an empty string. The algorithm must handle s = "" or t = "" gracefully.
• Single character strings: When both strings are single characters, the solution must correctly identify matches or mismatches.

Duplicate Values and Repeated States

• Duplicate characters in t: If t contains duplicate characters (e.g., "aab"), the window must contain at least as many occurrences of each character in t.
• Character frequency mismatches: The sliding window approach must track exact character counts, not just presence, to avoid false positives.

Boundary Conditions

• t longer than s: If the target string is longer than the source, no valid window exists, so return an empty string.
• No valid substring: When s doesn't contain all characters of t, return an empty string.
• Exact match: When s equals t, the entire string is the answer.

Common Implementation Mistakes

• Incorrect character counting: Using a simple Set or boolean flags instead of frequency maps leads to incorrect window validation.
• Off-by-one errors in window bounds: Mismanaging left and right pointer updates can cause missing valid windows or including invalid ones.
• Not resetting minimum window: Failing to update the result when a smaller valid window is found can lead to returning incorrect results.
• Improper handling of character removal: When shrinking the window, ensure that character counts are decremented correctly to maintain valid state.

// Example edge case handling:
// s = "a", t = "aa" → returns ""
// s = "ab", t = "b" → returns "b"
// s = "a", t = "a" → returns "a"

9. Alternative Approaches

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

1. Brute Force with Character Frequency Counting

• Check every possible substring and verify if it contains all characters from the target string with required frequencies
• Time complexity: O(n³) - O(n²) substrings, each requiring O(n) verification
• Space complexity: O(1) additional space
• This approach is inefficient but conceptually simple and can serve as a baseline for correctness testing

2. Sliding Window with HashMap for Character Counting

• Use a HashMap to maintain character frequencies in both the target string and current window
• Expand window by moving right pointer until all characters are included, then contract from left while maintaining validity
• Time complexity: O(n) where n is the length of the input string
• Space complexity: O(k) where k is the number of unique characters in the target string

3. Two Pointers with Array Instead of HashMap

• If we know the character set is limited (e.g., only lowercase letters), use an array of size 256 for character counting
• This reduces HashMap overhead and provides faster access times
• Time complexity: O(n)
• Space complexity: O(1) since array size is fixed regardless of input

4. Binary Search on Window Size

• Binary search on the possible window sizes, checking if a valid window of that size exists
• For each candidate size, use sliding window to verify existence
• Time complexity: O(n log n) where n is the length of input string
• Space complexity: O(k) for character frequency storage

The chosen sliding window approach with HashMap is preferred because it provides optimal O(n) time complexity while being readable and maintainable. The array-based alternative offers better constant factors but requires knowledge of the character set, making it less general. The binary search approach introduces unnecessary complexity for this problem's constraints.

The HashMap-based sliding window solution strikes the best balance between performance, readability, and generality for production code at FAANG companies.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        String s1 = "ADOBECODEBANC";
        String t1 = "ABC";
        // Expected: "BANC" (length 4)
        System.out.println("Test 1: " + new Solution().minWindow(s1, t1));
        
        // Test case 2: No valid window exists
        String s2 = "a";
        String t2 = "aa";
        // Expected: "" (empty string)
        System.out.println("Test 2: \"" + new Solution().minWindow(s2, t2) + "\"");
        
        // Test case 3: Exact match
        String s3 = "abc";
        String t3 = "abc";
        // Expected: "abc"
        System.out.println("Test 3: " + new Solution().minWindow(s3, t3));
        
        // Test case 4: Multiple valid windows - should return earliest
        String s4 = "ab";
        String t4 = "b";
        // Expected: "b"
        System.out.println("Test 4: ":
        
        // Test case 5: Empty input string
        String s5 = "";
        String t5 = "A";
        // Expected: ""
        System.out.println("Test 5: \"" + new Solution().minWindow(s5, t5) + "\"");
        
        // Test case 6: Empty target string
        String s6 = "ADOBECODEBANC";
        String t6 = "";
        // Expected: ""
        System.out.println("Test 6: \"" + new Solution().minWindow(s6, t6) + "\"");
        
        // Test case 7: Complex case with duplicates
        String s7 = "aaflslfeegfweafkafldsfalfd";
        String t7 = "flfd";
        // Expected: "flfd"
        System.out.println("Test 7: " + new Solution().minWindow(s7, t7));
    }
}

Representative Test Cases:

1. Basic functionality: s = "ADOBECODEBANC", t = "ABC" → "BANC"
2. No solution exists: s = "a", t = "aa" → ""
3. Exact match: s = "abc", t = "abc" → "abc"
4. Single character target: s = "ab", t = "b" → "b"
5. Empty inputs: Either string is empty → ""
6. Complex duplicate handling: s = "aaflslfeegfweafkafldsfalfd", t = "flfd" → "flfd"

Tricky Case:

• Duplicate characters in target: When t contains repeated characters like "aab" and s has only one 'a', the window must contain at least two 'a' characters to satisfy the requirement.

Boundary Case:

• Target string longer than source: s = "ab", t = "abc" → "" (no valid window exists)

These test cases cover the key scenarios including edge cases, empty inputs, and various combinations of character frequencies that can occur in this sliding window problem.

11. Final Summary

The core insight is to use a sliding window technique with two pointers to find the minimum substring that contains all characters of the target string, achieving optimal O(n + m) time complexity where n and m are the lengths of the input and target strings respectively.

This solution works by maintaining a window that expands to include new characters and contracts when all required characters are present, using character frequency maps to efficiently track what's missing. The key efficiency comes from avoiding redundant character counting through the sliding window invariant that only expands when necessary and contracts as soon as all requirements are met.

What makes this solution efficient is its single-pass nature with constant-time character frequency updates, avoiding the need for multiple iterations or complex data structures. The approach is optimal because we must examine each character at least once to determine if it contributes to a valid window, making O(n + m) the best possible time complexity for this problem.