Minimum Window Substring: Combining Sliding Window and Two Pointers

26

Hard problems often require combining multiple algorithmic concepts. The minimum window substring problem demonstrates this perfectly—you need to merge the sliding window technique with the two-pointer approach to achieve an efficient linear-time solution. Let’s explore how these concepts work together to solve this challenging problem.

Understanding the Problem

You receive two strings: `s` (the source string) and `t` (the target string). Your task is to find the minimum window substring in `s` that contains all characters present in `t`.

Important considerations:

• Characters in `t` can appear multiple times, and your window must contain at least that many occurrences
• The substring must be contiguous
• If no valid window exists, return an empty string

For example,

If `s = “ADOBECODEBANC”` and `t = “ABC”`, the minimum window is `”BANC”` with length 4.

If `s = “CADA”` and `t = “CAAD”`, the minimum window is `”CADA”` with length 4, containing two A’s, one C, and one D.

Approach 1: Brute Force Method

The most straightforward approach involves checking all possible substrings starting from the minimum possible length.

Start with substrings of length equal to `t.length()`, since the answer cannot be smaller. Check each substring to see if it contains all required characters. If no valid substring exists at this length, increase the length and repeat.

For each substring, you need to verify it contains all characters from `t`. This requires comparing character frequencies, which takes O(26) or O(256) time depending on the character set—essentially constant time.

However, you’re checking O(n^2) substrings in the worst case, making this approach inefficient.

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Sliding Window with Two Pointers (Optimal Solution)

The key insight: use a variable-size sliding window with two pointers. Expand the window until it contains all required characters, then contract it to find the minimum valid window.

Character Frequency Maps

Before diving into the algorithm, understand how to efficiently compare character frequencies. Create frequency maps for both strings, storing the count of each character. Since we’re dealing with a limited character set (26 letters or 256 ASCII characters), comparing these maps takes constant time O(1).

For a valid window, the frequency of each character in the window must be at least equal to its frequency in `t`. Characters can appear more times than required, but not fewer.

The Algorithm

The solution uses two pointers (`left` and `right`) to maintain a sliding window:

1. Initialize: Create frequency maps for string `t` and an empty map for the current window
2. Expand phase: Move the `right` pointer, adding characters to the window map until all characters from `t` are present
3. Contract phase: Once valid, move the `left` pointer to shrink the window while maintaining validity
4. Track minimum: Keep track of the minimum window length and its boundaries

Step-by-Step Execution

Let’s trace through an example with `s = “AEBDECBCBA”` and `t = “ABCC”`:

Step 1 – Expand: Start with an empty window. Add characters one by one, updating the frequency map. Continue until you have at least one A, one B, and one C.

Step 2 – Contract: Once you have a valid window, try to shrink it from the left. Remove characters that don’t break the validity condition. If removing a character makes the window invalid, stop contracting.

Step 3 – Update minimum: After contracting, record this window if it’s smaller than the current minimum.

Step 4 – Continue: Expand the window again by moving the right pointer, then repeat the contract process.

Key Implementation Details

The comparison function checks if the window map contains at least the required frequency for each character in `t`:

• For each character in `t`, verify that `windowFrequency[char] >= targetFrequency[char]`
• If all characters satisfy this condition, the window is valid
• This comparison runs in constant time since we’re checking at most 256 characters

When expanding, increment the frequency of the character at `right`. When contracting, decrement the frequency of the character at `left` before moving the pointer.

Why This Works

The algorithm guarantees finding the minimum window because:

• It explores all valid windows systematically
• Contracting ensures you find the smallest valid window starting at each position
• The two-pointer approach eliminates redundant checks
• Character frequency maps enable constant-time validity checks

Time Complexity: O(n) – Each character is visited at most twice (once by each pointer)
Space Complexity: O(1) – Only constant space for frequency maps

Edge Cases

Handle these scenarios:

• No valid window: If `s` doesn’t contain all characters from `t`, return an empty string
• Single character: If `t` has multiple occurrences of a character that `s` doesn’t have enough of, return empty string
• Exact match: If `s` equals `t`, return `s` itself

Why This Problem Matters

This problem demonstrates several important concepts:

• Sliding window pattern: When you see “substring” or “contiguous,” think sliding window
• Variable window size: The window expands and contracts based on conditions
• Two pointers: Efficiently traverse the array without redundant checks
• Character frequency maps: Enable constant-time comparisons for string problems

Combining these techniques transforms an O(n^2) solution into an O(n) solution, showcasing the power of algorithmic thinking.

Video Explanation

If you need personalized guidance on solving this problem or preparing for coding interviews, you can schedule a one-on-one session to discuss your specific questions.

For more coding solutions and resources, check out my GitHub repository and all my helpful resources.