Sliding Window — Minimum Window Subsequence

↗ LeetCode: Minimum Window Subsequence · Hard · pattern chapter →

Find the min window in s1 such that s2 is a subsequence.

Example 1 — s1="abcdebdde", s2="bde" → "bcde"Example 2 — s1="jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2="k" → "k"

Constraints — 1 ≤ |s1| ≤ 2·10⁴; 1 ≤ |s2| ≤ 100. Brute enumerates windows and matches subseq — O(n²·m) = 10¹⁰ ops at n=2·10⁴ (TLE). Two-pointer scan with backwards refine is O(n·m) = ~4·10⁶ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — DP `dp[i][j]` = latest start of match

O(m·n) time and space.

Approach 2 — Two-pointer forward + backward (canonical)

Insight. Advance i in s1 matching s2 chars in order. On full match, walk backward from end index to shrink to minimal window that still contains s2 as subsequence. Repeat.

java

String minWindow(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int bestLen = Integer.MAX_VALUE, bestStart = -1;
    int i = 0;
    while (i < m) {
        int j = 0;
        while (i < m) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
                if (j == n) break;
            }
            i++;
        }
        if (i == m) break;
        int end = i;
        j = n - 1;
        while (j >= 0) {
            if (s1.charAt(i) == s2.charAt(j)) j--;
            i--;
        }
        i += 2;
        int start = i - 1;
        if (end - start + 1 < bestLen) { bestLen = end - start + 1; bestStart = start; }
    }
    return bestStart < 0 ? "" : s1.substring(bestStart, bestStart + bestLen);
}

Execution Trace

Forward + backward — s1='abcdebdde', s2='bde'

Step 1 / 3forward: full match at idx 4 (a-b-c-d-e)

Complexity — Time O(m · n) worst; often much faster.

Try it yourself

Complexity summary

Approach	Time	Space	Grade
DP	O(m·n)	O(m·n)	works
2p forward+backward	O(m·n) worst	O(1)	canonical

When to use which

Subsequence (order matters) → this pattern.
Substring (set membership) → Minimum Window Substring.
"Any window containing s2" → forward sweep only.

✨AI Study CompanionBeta

Was this page helpful?

Sliding Window — Minimum Window Subsequence ​

Approach 1 — DP dp[i][j] = latest start of match ​

Approach 2 — Two-pointer forward + backward (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​