Minimum Window Subsequence

Master this topic with zero to advance depth.

Minimum Window Subsequence

Given strings s1 and s2, find the minimum contiguous substring of s1 such that s2 is a subsequence of that part.

Visual Representation

s1 = "abcdebdde", s2 = "bde"

Forward (Find b...d...e):
a b c d e b d d e
  ^     ^       ^    (Found at index 4, end=5)

Backward (Optimize Start from index 4):
a b c d e
  ^     ^            (Start=1, b is at idx 1)

Result: "bcde" (Len 4)

Hard

Examples

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

Approach 1

Level I: Brute Force

Intuition

For every possible starting point in s1, scan forward to see if s2 can be formed as a subsequence. If it can, record the length and update the minimum window found so far.

Thought Process

Iterate through all indices i in s1 as potential starts.
From i, use another pointer k to scan s1, and j to scan s2.
If s1[k] == s2[j], increment j.
If j == s2.length(), we found a window [i, k]. Its length is k - i + 1.
Track the minimum such length and the starting position.

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

Detailed Dry Run

Start	s1 Scan	s2 Matched	Window	Min
1 (b)	bcde	b, d, e (All)	[1, 4]	4
5 (b)	bdde	b, d, e (All)	[5, 8]	4

java

public class Main {
    public static String minWindow(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        String res = "";
        int minLen = n + 1;

        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) == s2.charAt(0)) {
                int s1Idx = i, s2Idx = 0;
                while (s1Idx < n && s2Idx < m) {
                    if (s1.charAt(s1Idx) == s2.charAt(s2Idx)) s2Idx++;
                    s1Idx++;
                }
                if (s2Idx == m) {
                    if (s1Idx - i < minLen) {
                        minLen = s1Idx - i;
                        res = s1.substring(i, s1Idx);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(minWindow("abcdebdde", "bde")); // "bcde"
    }
}

Approach 2

Level II: Dynamic Programming (O(N * M))

Intuition

We can use a 2D DP table dp[i][j] that stores the starting index of the shortest substring in s1[0...i] such that s2[0...j] is a subsequence. If no such substring exists, we store -1.

Thought Process

dp[i][0] is i if s1[i] == s2[0], else dp[i-1][0].
For j > 0, if s1[i] == s2[j], then dp[i][j] = dp[i-1][j-1] (we extend the subsequence start index from the previous match).
Otherwise, dp[i][j] = dp[i-1][j] (we inherit the latest start index).

Pattern: Subsequence Search with DP

⏱ O(N * M)💾 O(N * M) - Can be optimized to $O(N)$.

java

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

Approach 3

Level III: Optimal (Sliding Window + Dual Scan)

Intuition

Thought Process

Unlike 'Minimum Window Substring' (set of chars), this requires subsequence (specific order). We scan forward to find any window containing the subsequence. Once found, we scan backward from the current end to find the best starting point for that specific window.

Patterns

Forward Pass: Expand to find a valid window ending at i.
Backward Pass: From i, scan back to find the latest valid start j. This handles cases like S=abbbcde, T=abcde more accurately by skipping redundant bs at the beginning of the window.

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

Detailed Dry Run

i	j	Action	Result
1	0	'b' matched	i=2, j=1
4	2	'e' matched	Window Found!
Backward	-	Scan back from i=4	Start=1
Min	-	Check "bcde"	MinLen=4

java

public class Main {
    public static 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;
                    j--; // Back to last matched index of s2
                    while (j >= 0) {
                        if (s1.charAt(i) == s2.charAt(j)) j--;
                        i--;
                    }
                    i++; j++; // i is now start, j is 0
                    if (end - i < minL) {
                        minL = end - i;
                        start = i;
                    }
                }
            }
            i++;
        }
        return start == -1 ? "" : s1.substring(start, start + minL);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("abcdebdde", "bde")); // "bcde"
    }
}

⚠️ Common Pitfalls & Tips

The backward scan is crucial for finding the optimal start. Without it, you might find a valid window but not the minimum one starting from a later occurrence of the first character.

← Previous QuestionSliding Window Maximum

Next Question →Maximum Points You Can Obtain from Cards

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.