mediumSliding WindowSliding Window

Minimum Window Substring

mediumTime: O(n + m)Space: O(m)

Recognize the pattern

shortest substring containing all characters of tvariable-size windowcharacter frequency tracking

Brute force idea

A straightforward first read of Minimum Window Substring is this: Check every substring of s for containing all characters of t. Each substring is checked independently. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

Better approach

The deeper shift in Minimum Window Substring is this: Sliding window with two pointers: expand right to include characters, shrink left to minimize length while still containing all of t. Track character counts and a 'formed' counter. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Key invariant

At the center of Minimum Window Substring is one steady idea: The window is valid when it contains at least as many of each character as t requires. Expand to make it valid, shrink to minimize it, and track the smallest valid window seen. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Watch out for

One easy way to drift off course in Minimum Window Substring is this: Comparing full frequency maps at every step — track a 'formed' count that increments when a character's window frequency meets its required frequency. This makes each step. The fix is usually to return to the meaning of each move, not just the steps themselves.

Sliding Window Pattern