AlgoViz
HomeSliding Window

Minimum Window Subsequence

Hard

Walk forward to match, backward to tighten

Problem

Find the smallest substring of S that contains T as a subsequence (keeping T's order).

In simple words

March forward to match T, then march backward to tighten the window's start.

The idea

Unlike the substring version, order matters and gaps are allowed, so a frequency window does not apply. Sweep forward matching T's characters in order; on completing a match, walk backwards matching T in reverse to find the tightest start, then continue from just after it.

The trick

  • Two-directional scan: forward to find an end, backward to pull the start in.
  • Restart the next search from the position after the tightened start.
  • O(n·m) in the worst case; DP gives the same bound more predictably.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — S='abcdebdde', T='bde' Values: 0.

1/2
Optimal
timeO(n*m)spaceO(1)
1two pointers: advance to match all of T, then shrink from left keeping T matched2track the shortest valid window

Input

array
[0]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
S='abcdebdde', T='bde'
Output:
'bcde'

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.