AlgoMaster Logo

Minimum Window Substring

Last Updated: April 9, 2026

hard
4 min read

Understanding the Problem

We need to find the shortest contiguous substring of s that contains every character in t, counting duplicates. So if t = "AAB", our window must contain at least two 'A's and one 'B'.

Notice that order doesn't matter. We're not looking for t as a subsequence in some particular arrangement. We just need the right characters in the right quantities. This is fundamentally a frequency-matching problem layered on top of a substring search.

The key observation: once we find a valid window, we can try shrinking it from the left to find a smaller one. And once the window becomes invalid, we expand it from the right. This expand-then-shrink pattern is the signature of a sliding window approach.

Key Constraints:

  • m and n can be up to 10^5 → An O(m^2) brute force that checks every substring is borderline, and verifying each substring adds more cost. We need something closer to O(m).
  • Characters are uppercase and lowercase English letters → Only 52 possible characters, so frequency arrays of fixed size are feasible.
  • Duplicates in t matter → We need frequency counts, not just a set of characters.

Approach 1: Brute Force

Intuition

The most straightforward approach: generate every possible substring of s and check whether it contains all the characters of t. Among all valid substrings, return the shortest one.

To check whether a substring contains all characters of t, we compare character frequencies. Build a frequency map for t, build one for the substring, and verify that every character in t appears at least as many times in the substring.

Algorithm

  1. Build a frequency map for t
  2. For each starting index i from 0 to m - 1
  3. For each ending index j from i to m - 1, maintain a running frequency map of s[i..j]
  4. After adding s[j], check if the current window satisfies all frequency requirements of t
  5. If it does and the window is smaller than the best so far, update the result
  6. Return the smallest valid window found, or "" if none exists

Code

The bottleneck is that for every starting position i, we expand rightward until we find a valid window, then move to i + 1 and start scanning rightward again from scratch. What if instead of restarting, we just shrank the window from the left?

Approach 2: Sliding Window

Intuition

Instead of restarting a fresh window for every starting position, we maintain a single window defined by two pointers, left and right. We expand right to include more characters until the window is valid (contains all of t). Then we shrink left to try to make the window smaller while keeping it valid. Every time we have a valid window, we check if it's the smallest we've seen.

The trick to making the validity check O(1) is tracking a counter called formed. We count how many distinct characters in t have their frequency requirement fully met by the current window. When formed equals the number of distinct characters in t, the window is valid. Each time we add or remove a character, we only need to update one frequency and potentially increment or decrement formed.

Algorithm

  1. Build a frequency map tCount for t. Count the number of distinct characters in t as required
  2. Initialize left = 0, formed = 0, and a window frequency map windowCount
  3. Expand right from 0 to m - 1:
    • Add s[right] to windowCount
    • If windowCount[s[right]] now equals tCount[s[right]], increment formed
  4. While formed == required (window is valid):
    • Update the result if this window is smaller than the current best
    • Remove s[left] from windowCount
    • If windowCount[s[left]] drops below tCount[s[left]], decrement formed
    • Move left forward
  5. Return the smallest window found

Code

The sliding window approach is already O(m + n), so we can't improve the asymptotic complexity. But when s contains many characters not in t, we waste time stepping through irrelevant positions. What if we could skip over characters that don't appear in t at all?

Approach 3: Optimized Sliding Window (Filtered)

Intuition

When s is much longer than t and contains many characters not in t, the standard sliding window wastes time stepping through irrelevant positions. We can pre-filter s to create a list of only the positions (and characters) that appear in t. Then we apply the exact same sliding window logic on this filtered list.

For example, with s = "XXXXAXXXXBXXXXCXXXX" and t = "ABC", the filtered list would be [(4,'A'), (9,'B'), (14,'C')]. The sliding window runs on 3 elements instead of 19.

This doesn't change the worst-case complexity (if every character in s is in t, the filtered list is the same size as s). But in practice, when s has many irrelevant characters, this runs significantly faster.

Algorithm

  1. Build a frequency map tCount for t
  2. Create a filtered list of (index, character) pairs from s, keeping only characters that appear in t
  3. Apply the sliding window on the filtered list:
    • Expand right to include more entries until the window is valid
    • Shrink left while the window remains valid
    • The actual window in s spans from filtered[left].index to filtered[right].index
  4. Return the smallest window found

Code