AlgoMaster Logo

Minimum Window Subsequence

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This problem asks us to find the shortest substring of s1 that contains s2 as a subsequence, not as a substring. That distinction is critical. A subsequence means the characters of s2 must appear in s1 in the same order, but they don't need to be contiguous. The window, however, must be contiguous since it's a substring of s1.

So we're looking for a contiguous chunk of s1 where, if we scan through it, we can pick out all the characters of s2 in order. Among all such chunks, we want the shortest one, and if there are ties, the leftmost.

The problem blends two ideas: subsequence matching, where order matters but gaps are allowed, and window minimization, where we want the smallest contiguous range. Handling both at once is what makes it harder than a plain substring search.

Key Constraints:

  • 1 <= s1.length <= 2 * 10^4. With n up to 20,000, an O(n^2) scan (around 4 10^8 operations) is borderline but passes, and an O(n m) solution with m up to 100 is comfortable.
  • 1 <= s2.length <= 100. Since s2 is short, using its length as a second dimension (an n * m table or an m-length pointer) stays cheap.
  • Lowercase English letters only, so there are 26 distinct characters.

Approach 1: Brute Force

Intuition

Check every possible starting position in s1 and, from each one, try to match s2 as a subsequence going forward. Among all starts that produce a valid match, keep the shortest window, breaking ties toward the smaller starting index.

For a fixed start i, we walk forward through s1 with a pointer k into s2. Each time the current character of s1 equals s2[k], we advance k. When k reaches the end of s2, every character of s2 has been matched in order, and s1[i..j] (where j is the current position) is a valid window. Because the match for index i is greedy and stops as soon as s2 is complete, the first j we reach is the shortest window starting at i.

This re-scans the same characters from every starting position, so it does a lot of repeated work.

Algorithm

  1. For each starting index i from 0 to len(s1) - 1:
    • If s1[i] does not match s2[0], skip this starting index.
    • Otherwise, try to match all characters of s2 by scanning forward through s1 from index i.
    • Use a pointer k for s2. For each character in s1[i..], if it matches s2[k], advance k.
    • If k reaches len(s2), we found a valid window from i to the current position in s1.
    • Track the minimum window length and its starting index.
  2. Return the minimum window, or "" if none was found.

Visualization and Code

Loading animation...

The redundant scanning comes from restarting at every index. The next approach scans s1 once to find where a valid window ends, then walks backward from that endpoint to pull the start as far right as possible.

Approach 2: Forward-Backward Sliding Window

Intuition

When a forward scan first completes a match of s2, the endpoint it lands on is the earliest possible right edge for that scan, but the left edge is often too far back. The start can be pushed rightward while s2 is still a subsequence.

So we run a two-phase scan:

  1. Forward pass: Scan right through s1, advancing a pointer into s2 on each match. When the last character of s2 matches, the current index is the right endpoint of a valid window.
  2. Backward pass: From that endpoint, scan left through s1, matching s2 in reverse. When the first character of s2 matches, the current index is the rightmost start that still keeps s2 a subsequence ending at that endpoint. That gives the shortest window for this endpoint.

After recording the tightened window, we restart the forward pass at left + 1 and repeat until no further window exists.

The backward pass is what minimizes each window. Matching s2 in reverse from the endpoint asks for the latest start index from which s2 can still be read off in order up to the endpoint, so no shorter window can end there.

Algorithm

  1. Initialize a pointer i = 0 to scan through s1, and variables to track the best window.
  2. While i < len(s1):
    • Forward pass: Use a pointer j for s2. Scan s1 forward from i. Whenever s1[i] matches s2[j], advance j. Keep advancing i until j reaches len(s2) (all characters matched) or i reaches the end.
    • If we didn't match all of s2, break (no more valid windows exist).
    • Record the right endpoint right = i.
    • Backward pass: Reset j to len(s2) - 1. Scan s1 backward from right. Whenever s1[right] matches s2[j], decrement j. Keep going until j < 0.
    • Record the left endpoint left = current position.
    • The window s1[left..right] is a minimal window for this endpoint. Update the best if it's shorter.
    • Set i = left + 1 to search for the next potential window.
  3. Return the best window, or "" if none found.

Visualization and Code

Loading animation...

The forward-backward approach recomputes overlapping windows from scratch each time. The next approach records, for every position in s1 and every prefix of s2, where the best matching window started, so each window is built once in a single table-filling pass.

Approach 3: Dynamic Programming

Intuition

Instead of scanning forward and backward, the DP approach builds a table that records, for each position i in s1 and each prefix length j+1 of s2, the start index of a window inside s1[..i] that contains s2[0..j] as a subsequence with its last matched character at position i or earlier.

Define dp[i][j] as the start index in s1 of such a window, or -1 if s2[0..j] cannot be matched within s1[0..i]. The recurrence has three cases:

  • s1[i] == s2[j] and j == 0: the first character of s2 matches here, so a window covering just s2[0] starts at i. Set dp[i][0] = i.
  • s1[i] == s2[j] and j > 0: matching s2[j] at i extends a window that already covered s2[0..j-1]. That earlier window ended at i - 1 or before, so its start is dp[i-1][j-1]. Set dp[i][j] = dp[i-1][j-1] (still -1 if no such window exists).
  • s1[i] != s2[j]: position i cannot match s2[j], so the best window for s2[0..j] is whatever it was one position back. Set dp[i][j] = dp[i-1][j].

After filling the table, each non-negative dp[i][m-1] marks a window ending at i with start dp[i][m-1]. Scanning the last column for the smallest i - dp[i][m-1] + 1 gives the answer, and scanning left to right keeps the leftmost start on ties.

Algorithm

  1. Create a 2D array dp of size n x m, initialized to -1 (meaning "no valid window found yet").
  2. Fill the table row by row (for each index i in s1):
    • For each index j in s2:
      • If s1[i] == s2[j]: if j == 0, set dp[i][j] = i. Otherwise if i > 0 and dp[i-1][j-1] != -1, set dp[i][j] = dp[i-1][j-1].
      • Else if i > 0: set dp[i][j] = dp[i-1][j].
  3. Scan through dp[i][m-1] for all i. For each valid entry, compute the window length. Track the minimum.
  4. Return the minimum window.

Visualization and Code

Loading animation...