Minimum Window Subsequence
WHAT IT SAYS
Given s1 and s2, find the shortest contiguous substring of s1 that contains s2 as a subsequence — same characters, same order, gaps allowed.
WHAT IT'S REALLY ASKING
"Order changes everything: a window can hold every character you need and still be worthless, so there's no tally that tells you whether you're valid. What you *can* do is be impatient — grab each needed character at the earliest moment it appears, which pins the earliest possible right end — then, having found an end, be impatient in reverse and grab each character at the latest moment, which pins the tightest possible left edge for that end."
Start everywhere, match forward, take the earliest finish
O(n · m) time, O(1) spaceFor each start i, walk forward through s1 with a pointer into s2, consuming a character of s2 whenever it matches. Wherever s2 runs out, that's the shortest window starting at i. Do that for all n starts and keep the smallest.
WHERE THE WORK IS WASTED — Most starts are stillborn: any i where s1[i] isn't the character s2 begins with produces a window whose first character is dead weight — it is strictly worse than the window starting at the next occurrence of s2[0], and yet you scan the whole thing anyway. And the scans overlap almost entirely; the pass from i and the pass from i + 1 walk the same characters and consume s2 in nearly the same places, one shifted. You are enumerating n windows when only a handful of them are ever tight on both sides.
Grab early to find the end; grab late to tighten.
First, why the previous problem's machinery dies here. When the requirement was a multiset, a window's validity was a tally, so you could shrink from the left and re-test in O(1). Order destroys that: 'bde' inside 'edb' has every character and matches nothing. Validity now depends on *where* the characters sit relative to one another, so there is no counter to maintain — you have to actually re-derive an embedding. So derive it greedily, and justify the greed with an exchange argument. Suppose you're scanning forward from some point and you always consume the *earliest* occurrence of the next character of s2. Claim: if any valid embedding exists ahead of you, the greedy one finishes no later than it. Take any other embedding and find the first position where it differs from greedy: greedy's pick sits at or before the other's, and the rest of the other embedding is still entirely available after greedy's earlier pick — so you can swap it in and never finish later. Repeat the swap; greedy dominates. Impatience is safe. Now mirror it. Once greedy-forward hands you an end index e, run the same argument backwards from e: consume s2 from its last character to its first, always taking the *latest* occurrence. By the same exchange, this pins the largest possible start for that particular end — the tightest window ending at e. There is therefore exactly one candidate window per right end, and both of its edges are found by pure greed, one sweep in each direction. The answer is the smallest of those candidates.
Forward to a finish, backward to a squeeze, then step and repeat
O(n · m) worst case, O(1) spaceSweep forward matching s2 greedily; the moment s2 is exhausted, freeze that index as the right end and walk backwards matching s2 in reverse until it's exhausted again — where you land is the tightest left edge for that end. Record the window, then resume the forward sweep from one past that left edge, with s2 reset. Each restart is guaranteed to look for a genuinely different window, and the smallest one you ever record is the answer.
The same greed, memoised
O(n · m) time, O(m) space with a rolling rowLet dp[i][j] be the largest starting index of a window inside s1[0..i] that contains the first j characters of s2 as a subsequence. If s1[i] equals s2[j], the only way to use it is to consume it, so dp[i][j] = dp[i−1][j−1]; otherwise s1[i] is a passenger and dp[i][j] = dp[i−1][j]. Read the answer off the last column: the best i minus dp[i][m] plus one — the table is just the backward greed, computed for every prefix at once.
Two-Way Greed
YOU'LL SEE IT AGAIN WHEN
- The requirement is order-sensitive — a subsequence, a pattern, a sequence of events — so no frequency tally can decide whether a window qualifies.
- You want the shortest window containing the pattern, and 'contains it' is checkable by a single greedy left-to-right sweep.
- Greedy-earliest can be defended by an exchange argument: swapping a later choice for the earlier one leaves the rest of the match intact.
- The window's two edges answer different questions — the earliest end, then the latest start for that end — so one pass in each direction pins it.