Course4all
Join us on telegram
Home/dsa/Two Pointers/Minimum Window Subsequence

Minimum Window Subsequence

Master this topic with zero to advance depth.

Minimum Window Subsequence

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part. If there is no such window, return an empty string.

Visual Representation

s1 = "abcdebdde", s2 = "bde" Forward Pass: a b c d e b d d e ^ ^ ^ b...d.e (Found at res[1...5]) Backward Pass (Optimization): From index 4, look for 'e', then 'd', then 'b' backwards. Found 'b' at index 1 -> Best Window: "bcde"
Hard

Examples

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

"bcde" is the smallest substring of s1 where "bde" is a subsequence.

Approach 1

Level I: Brute Force

Intuition

Check every possible substring of s1 and verify if s2 is a subsequence of that substring.

⏱ O(N^2 * M)💾 O(1)

Detailed Dry Run

s1="abcde", s2="bde". Substrings: "a", "ab", "abc", "abcd", "abcde" (Check "abcde": "b","d","e" found! Length 5). Next index...

java
public String minWindow(String s1, String s2) {
    String res = "";
    int minLen = s1.length() + 1;
    for (int i = 0; i < s1.length(); i++) {
        for (int j = i; j < s1.length(); j++) {
            if (isSubsequence(s2, s1.substring(i, j + 1))) {
                if (j - i + 1 < minLen) {
                    minLen = j - i + 1;
                    res = s1.substring(i, j + 1);
                }
            }
        }
    }
    return res;
}

⚠️ Common Pitfalls & Tips

O(N^2 * M) is extremely slow and will time out.

Approach 2

Level II: Better (Dynamic Programming)

Intuition

We can use DP where dp[i][j] stores the starting index of the shortest substring in s1[0..j] that contains s2[0..i] as a subsequence.

If s1[j] == s2[i], then dp[i][j] = dp[i-1][j-1]. Otherwise, dp[i][j] = dp[i][j-1].

⏱ O(N * M)💾 O(N * M) or O(N)

Detailed Dry Run

s1 = 'abcde', s2 = 'bde'. DP table tracks the best starting index for every prefix of s2 found in s1.

java
public String minWindow(String s1, String s2) {
    int m = s2.length(), n = s1.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int j = 0; j <= n; j++) dp[0][j] = j + 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(j-1) == s2.charAt(i-1)) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = dp[i][j-1];
        }
    }
    int start = 0, len = n + 1;
    for (int j = 1; j <= n; j++) {
        if (dp[m][j] != 0) {
            if (j - dp[m][j] + 1 < len) {
                len = j - dp[m][j] + 1; start = dp[m][j] - 1;
            }
        }
    }
    return len == n + 1 ? "" : s1.substring(start, start + len);
}

⚠️ Common Pitfalls & Tips

Space complexity O(N*M) can be reduced to O(N).

Approach 3

Level III: Optimal (Two Pointers - Two Way Scan)

Intuition

Finding a subsequence window can be done by scanning forward to find any valid window and then scanning backward to minimize the window size from the starting side. This is more efficient than a simple sliding window because subsequence requirements are more flexible than substring requirements.

  1. Scan s1 forward matching characters of s2 one by one. Once all characters are matched, we have a valid ending index.
  2. Move backward from the ending index matching characters of s2 in reverse to find the latest possible start index for this specific end index.
  3. Record the window, shrink the search space, and repeat.
⏱ O(N * M)💾 O(1)

Detailed Dry Run

s1 = 'abcdebdde', s2 = 'bde'.

  • Forward: find 'b'(1), 'd'(3), 'e'(4). end=5.
  • Backward from index 4: 'e'(4), 'd'(3), 'b'(1). start=1. Window [1, 5)='bcde'.
java
public class Solution {
    public String minWindow(String s1, String s2) {
        int i = 0, j = 0, start = -1, minL = s1.length() + 1;
        while (i < s1.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                if (++j == s2.length()) {
                    int end = i + 1;
                    for (j--; j >= 0; i--)
                        if (s1.charAt(i) == s2.charAt(j)) j--;
                    i++; j++;
                    if (end - i < minL) { minL = end - i; start = i; }
                }
            }
            i++;
        }
        return start == -1 ? "" : s1.substring(start, start + minL);
    }
}

⚠️ Common Pitfalls & Tips

Ensure the backward pass correctly identifies the latest start index. O(N*M) is the standard solution.

← Previous QuestionShortest Palindrome
Next Question →Longest Substring with At Most K Distinct Characters