483. Minimum Window Subsequence
You are given two strings of lowercase letters, s1 and s2. Among all contiguous substrings (windows) of s1 that contain s2 as a subsequence — meaning you could delete some characters of the window, without reordering the rest, and be left with exactly s2 — return the shortest one.
Two tie-breaking rules pin the answer down:
- If several windows share the minimum length, return the one that begins earliest in
s1. - If no window of
s1containss2as a subsequence, return the empty string"".
Note the twist versus the classic minimum-window problem: s2 must appear in order inside the window, not merely as a multiset of characters.
Example 1:
Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: Deleting "c" from the window "bcde" leaves "bde", so "bde" is a subsequence of it. The window "bdde" (further right) also works and is also length 4, but "bcde" starts earlier, so it wins the tie.
Example 2:
Input: s1 = "stairwell", s2 = "wax"
Output: ""
Explanation: s1 contains no "x" at all, and its only "a" comes before its only "w", so "wax" can never appear in order. No window exists and the answer is the empty string.
Constraints:
- 1 ≤ s1.length ≤ 2 * 10⁴
- 1 ≤ s2.length ≤ 100
- s1 and s2 consist of lowercase English letters.
Hints:
Checking whether s2 is a subsequence of a window is a greedy left-to-right scan: always take the first match for the next needed character. As a first cut, run that scan from every possible start index of s1.
Suppose a forward scan starting at i first completes the match of s2 at index end. That window may be loose at the front — walk backward from end matching s2 in reverse; where the reverse match finishes is the tightest possible start for that end.
After recording the tightened window [start, end], the next candidate window must begin at start + 1 or later, so resume the forward scan there. For the DP angle instead: let dp[j] be the latest start position such that s2[0..j) is a subsequence of s1[start..i]; each new character of s1 updates dp right-to-left.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s1 = "abcdebdde", s2 = "bde"
Expected output: "bcde"