Find the minimum window substring.

Approach

Checking every substring of s takes at least quadratic time. A sliding window does better because of one property: if a window contains all of t, so does every larger window around it. So for each right end, you only need the smallest window that ends there, and the left end of that window never moves backward.

Grow the window one character at a time from the right. As soon as it contains all of t, record it if it's the shortest so far, then move the left end forward until the window is missing something. Then grow it from the right again.

To check whether the window is valid in constant time, keep a count of how many more of each character the window needs, starting from the counts in t, plus a single missing total. Adding a character that's still needed lowers missing. Removing a character that the window then needs again raises it. The window covers t exactly when missing is 0.

Steps

1. Count the characters of t into need, and set missing to the length of t.
2. Move right across s. If need for the new character is above 0, lower missing. Then lower that character's count, even if it goes negative.
3. While missing is 0, record the window if it's the shortest so far. Then raise the count of the character at left, raise missing if that count is now above 0, and move left forward.
4. Return the shortest window you recorded, or an empty string if there wasn't one.

Complexity

• Time: O(m + n), where m and n are the lengths of s and t. Each pointer moves across s at most once.
• Space: O(k), where k is the number of distinct characters. With only English letters, that's constant.

Common mistakes

• Treating t as a set of characters. If t is "aa", the window needs two a characters, so track counts, not just presence.
• Lowering missing for every character you add. Only characters the window still needs count, which is why need is checked before it's lowered.
• Recording the window after shrinking it instead of before. The step that makes missing positive also makes the window invalid.