Coding Interview PatternsMinimum Window Subsequence
HardSliding Window

Minimum Window Subsequence

Explanation & Solution

Practice Problem

Description

Given strings s1 and s2, return the minimum contiguous substring of s1 such that s2 is a subsequence of the substring. If there is no such window, return an empty string "".

If there are multiple minimum-length windows, return the one that occurs first (leftmost).

Input: s1 = "abcdebdde", s2 = "bde"

Output: "bcde"

Explanation: "bcde" is the shortest substring of s1 where "bde" is a subsequence: b→d→e. Another candidate "bdde" has the same length but starts later.

Constraints

  • 1 <= s1.length <= 2 * 10^4
  • 1 <= s2.length <= 100
  • s1 and s2 consist of lowercase English letters.

Approach

Sliding Window pattern

1. Forward Pass — Find a Subsequence Match

  • Starting from index i, scan forward through s1 to find all characters of s2 in order.
  • Use pointer j for s2: whenever s1[start] === s2[j], advance j.
  • If j reaches s2.length, we found a valid window ending just before start.
  • If j never reaches s2.length, no more matches are possible — stop.

2. Backward Pass — Optimize the Window

  • After finding a match ending at index start - 1, trace backward through s1 from that end.
  • Match s2 characters in reverse: starting from s2[s2.length - 1] back to s2[0].
  • This finds the rightmost (latest) starting position for the subsequence, which gives the shortest window ending at this position.
  • The result is the optimized window [end, start).

3. Update the Minimum

  • Compare the current window length start - end with minLen.
  • If shorter, update minLen and minStart.

4. Advance and Repeat

  • Set i = end + 1 to search for the next potential window.
  • Repeat until no more subsequence matches are found.

5. Return the Result

  • If a valid window was found, return the substring from minStart with length minLen.
  • Otherwise return an empty string.

Key Insight

  • The critical insight is the backward optimization: after finding any valid window, tracing backward from the end gives the tightest possible window for that endpoint. This avoids checking all O(n^2) substrings and is much more efficient than a brute-force approach.
Time
O(n * m) where n = `s1.length` and m = `s2.length`. Each forward+backward pass takes at most O(n), and we advance `i` each iteration.
Space
O(1)only a few pointers.

Visualization

Input:
[a, b, c, d, e, b, d, d, e], s2 = bde
a0b1c2d3e4b5d6d7e8
—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone
20 steps

Solution Code

Previous
Substring with Concatenation of All Words