Minimum Window Substring — Step-by-Step Visualization

Algorithm Pattern

Sliding Window with Two Frequency Maps

Key Idea

We use two pointers to maintain a window. Expand the right pointer to include characters until the window is 'valid' (contains all target characters). Then contract the left pointer to find the smallest valid window.

Step-by-Step Approach

1. Create a frequency map for the target string 't'.
2. Use two pointers, L and R, initially at 0.
3. Iterate R across the source string 's', adding each character to a window frequency map.
4. Keep track of how many unique characters in the window meet the required frequency (HAVE vs NEED).
5. While HAVE equals NEED, the window is valid. Update the minimum result and shrink the window from the left by moving L.

Common Gotchas

• Wait until the count of a character in the window exactly matches its target count before incrementing 'HAVE'.
• Update the result only when a valid window is found, and ensure you store both the length and the boundaries.