DSA problem

Minimum Window Subsequence

HardSliding Window - Dynamic SizePattern: Two Pointers / Sliding Windowtop600GoogleAmazonMicrosoftDropbox

Given strings s1 and s2, return the minimum (contiguous) substring w of s1 such that s2 is a subsequence of w.

If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Note the key difference from "Minimum Window Substring": here s2 must appear as a subsequence (characters in order, not necessarily contiguous) inside the window, rather than as an unordered multiset of characters. The efficient solution uses a two-pointer forward-then-backward scan: move forward through s1 to find an end index that completes s2, then walk backward to tighten the start index to the smallest possible window.

Examples

Example 1

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

Output: "bcde"

Explanation: "bcde" is the answer because it occurs before "bdde" which has the same length. "deb" is not a smaller window because the elements of s2 in the window must occur in order.

Example 2

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"

Output: ""

Explanation: The character "u" never appears in s1, so no valid window exists.

Example 3

Input: s1 = "cnhczmccqouqadqtmjjzl", s2 = "mm"

Output: "mccqouqadqtm"

Explanation: The smallest window containing "m" then a later "m" as a subsequence runs from the first "m" to the last "m".

Constraints

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

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowstringtwo-pointersdynamic-programming

Browse all DSA problems