L12. Minimum Window Substring | Two Pointers and Sliding Window

This chapter covers the classic algorithmic problem of finding the Minimum Window Substring using Two Pointers and the Sliding Window pattern. We analyze the problem requirements, look at a naive brute-force approach, and then evolve it into an optimal $O(N)$ sliding window solution using a frequency hash map.

1. Problem Statement & Definition

You are given two strings:

• s: The source string to search within.
• t: The target string whose characters must all be present in the window.

Your objective is to find the minimum length substring in s that contains all characters of t (including duplicate occurrences as specified in t). If no such substring exists, return an empty string.

Note: Order does not matter, but frequencies do! If character b appears twice in t, your substring in s must contain at least two occurrences of b.

Real-Life Analogy: The Shopping List Audit

Imagine you are walking down a grocery aisle (s) holding a specific shopping list (t) that requires 1 apple, 2 bananas, and 1 cherry. You grab items as you walk forward until your basket satisfies the exact counts on your list. Once satisfied, you realize you picked up extra clutter at the beginning. You start dropping items from the front of your basket (shrinking the window) as long as your basket remains valid. Your goal is to find the shortest contiguous segment of aisle items that satisfies your shopping list.

2. Naive Brute-Force Approach ($O(N^2)$)

The initial approach that comes to mind is generating every possible contiguous substring of s, checking whether each substring contains all characters of t, and tracking the minimum length among all valid windows.

Programmatic Check Workflow

Limitations of Brute Force

• Time Complexity: $O(N^2)$ because generating all substrings takes quadratic time, and verifying each substring requires scanning characters.
• Interview Reality: Interviewers will immediately ask for an optimal linear-time solution since the problem involves finding a "minimum" and a "window". This naturally points toward the Sliding Window pattern.

3. Core Mental Model: The Sliding Window Technique

To optimize the solution to $O(N)$, we use two pointers—a Left (L) pointer and a Right (R) pointer—to dynamically expand and shrink our window.

Key Data Structures Required:

1. Hash Array / Map (hash[256]): Stores the frequency of characters from string t. As we expand R, we decrement frequencies. A positive value in the map indicates a required character has been matched.
2. count variable: Tracks how many unique or required characters from t have been successfully matched within the current window.
3. minLen & startIndex: Tracks the length and starting position of the optimal minimum window found so far.

4. Step-by-Step Execution Walkthrough

Let's trace how the optimal sliding window moves across s and t:

String s: D  D  A  A  B  C  ...
String t: A  B  C  (A:1, B:1, C:1)

1. Expand Right (R) pointer:
   - Encounter 'D': Not in `t` (hash value <= 0). Do not increment `count`. Decrement hash['D'].
   - Encounter 'A': Hash value is positive (pre-inserted from `t`). Increment `count` (count = 1), decrement hash['A'].
   - Continue expanding `R` until `count` equals the size of `t` (all characters found).

2. Shrink Left (L) pointer:
   - Once a valid window is found, try to minimize it by advancing `L` forward.
   - Remove leading characters that are unnecessary or exceed required counts until the window becomes invalid (`count` drops below target size).

3. Repeat Expansion and Shrinking:
   - Continue expanding `R` to find the next valid window, then shrink `L`.

5. Optimal Pseudo-Code ($O(N)$ Solution)

Here is the clean, production-ready algorithm implementing the sliding window approach:

string minWindow(string s, string t) {
    int hash[256] = {0};
    int m = t.size();
    int n = s.size();
    
    // Pre-insert all characters of T into the hash map
    for (int i = 0; i < m; i++) {
        hash[t[i]]++;
    }
    
    int l = 0, r = 0, minLen = 1e9, startIndex = -1, count = 0;
    
    while (r < n) {
        // If character at R was pre-inserted (positive value in hash), we found a target char
        if (hash[s[r]] > 0) {
            count++;
        }
        
        // Decrement frequency in map upon entry
        hash[s[r]]--;
        
        // When all characters of T are matched in the current window
        while (count == m) {
            // Update minimum length and starting index if current window is smaller
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                startIndex = l;
            }
            
            // Try to shrink from the left
            hash[s[l]]++;
            if (hash[s[l]] > 0) {
                count--; // Lost a required character
            }
            l++;
        }
        r++;
    }
    
    return startIndex == -1 ? "" : s.substr(startIndex, minLen);
}

6. Complexity Analysis

7. Summary and Key Takeaways

• Problem Definition: Find the shortest contiguous substring in s containing all characters and frequencies of t.
• Why Sliding Window?: Eliminates redundant $O(N^2)$ substring generations by maintaining a dynamic window bounded by left (L) and right (R) pointers.
• Role of the Hash Map: Pre-loaded with t character frequencies. Positive values indicate needed characters; zero or negative values indicate excess or non-target characters.
• The count Variable: Acts as a strict validation gate. When count equals m (size of t), the window is valid.
• Shrinking Phase: Once a valid window is established, increment L to drop redundant elements and minimize window length.
• Edge Case Handling: If startIndex remains -1 after traversal, no valid window exists, and an empty string is returned.