Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Dynamic Programming

Minimum Window Subsequence

hard

DESCRIPTION (credit Leetcode.com)

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

If there is no such substring, return an empty string "".

If there are multiple valid substrings of the same minimum length, return the one with the smallest starting index.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1

Input:

s1 = "abcdebdde"
s2 = "bde"

Output:

"bcde"

Explanation: "bcde" is the shortest substring of s1 that contains "bde" as a subsequence.

Example 2

Input:

s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl"
s2 = "u"

Output:

""

Explanation: "u" does not appear in s1, so there is no valid substring.

Explanation

This problem asks us to find the shortest substring of s1 that contains s2 as a subsequence (not a substring). A subsequence means the characters of s2 appear in s1 in the same order, but not necessarily consecutively.

For example, with s1 = "abcdebdde" and s2 = "bde":

"bcde" works because it contains b...d...e in order
"bdde" also works (b...d...e)
We want the shortest one: "bcde" (length 4)

Starting Simple: The Brute Force Approach

The most straightforward approach? Try every possible substring of s1 and check if s2 is a subsequence of it.

brute_force(s1, s2)
    for each starting position i in s1
        for each ending position j >= i
            if s2 is subsequence of s1[i:j+1]
                track if this is the shortest so far
    return shortest window

This works, but it's painfully slow. We're checking O(m²) substrings, and each subsequence check takes O(n) time. That's O(m²n) total - way too slow for large inputs.

A Smarter Approach: Forward Then Backward

Here's a better idea. Instead of checking random substrings, what if we:

Find where s2 ends - Scan forward through s1, matching characters of s2 one by one until we've matched all of s2
Shrink from the start - Once we've found a complete match ending at position i, walk backwards to find where this particular match started

This is more efficient because we're not checking unnecessary substrings. But there's still room for improvement - we might re-scan the same portions of s1 multiple times.

The Key Observation

Think about what information we actually need. When we're at position i in s1 and we find a character that matches s2[j]:

If this is the first character of s2 (j=0), we're starting a new potential window right here at position i
If this is a later character of s2 (j>0), we need to know: "Where did the window that matched s2[0..j-1] start?"

That second point is crucial. We don't need to re-scan backwards - we just need to remember where each partial match started.

Why Dynamic Programming?

This is exactly what DP is good for: remembering previous computations to avoid redoing work.

Let's define: dp[j] = the starting index in s1 from which we can form s2[0..j] ending at our current position.

When we find s1[i] == s2[j]:

If j == 0: This is the first character of s2, so dp[0] = i (start a new window here)
If j > 0: We extend a previous match, so dp[j] = dp[j-1] (the start position carries over from the previous match)

When dp[n-1] becomes valid (not -1), we've found a complete subsequence! The window goes from dp[n-1] to our current position i.

The DP array stores starting indices, not counts or boolean values. This lets us immediately compute the window length when we find a complete match.

Why Iterate Backwards Through s2?

We iterate j from n-1 down to 0 (backwards) because each dp[j] depends on dp[j-1]. If we iterated forwards, we'd overwrite dp[j-1] before using it for dp[j].

Walkthrough Example

Let's trace through s1 = "abcdebdde", s2 = "bde":

Initial state: dp = [-1, -1, -1] (no matches yet)

i=0 (s1[0]='a'): No matches with s2

i=1 (s1[1]='b'):

s1[1]='b' matches s2[0]='b'
dp[0] = 1 (new window starts at index 1)
dp = [1, -1, -1]

i=2 (s1[2]='c'): No matches

i=3 (s1[3]='d'):

s1[3]='d' matches s2[1]='d'
dp[1] = dp[0] = 1 (window still starts at 1)
dp = [1, 1, -1]

i=4 (s1[4]='e'):

s1[4]='e' matches s2[2]='e'
dp[2] = dp[1] = 1
dp = [1, 1, 1]
Complete match! Window from index 1 to 4: "bcde" (length 4)

i=5 (s1[5]='b'):

s1[5]='b' matches s2[0]='b'
dp[0] = 5 (new window starts at 5)
dp = [5, 1, 1]

i=6 (s1[6]='d'):

s1[6]='d' matches s2[1]='d'
dp[1] = dp[0] = 5
dp = [5, 5, 1]

i=7 (s1[7]='d'):

s1[7]='d' matches s2[1]='d'
dp[1] = dp[0] = 5
dp = [5, 5, 1]

i=8 (s1[8]='e'):

s1[8]='e' matches s2[2]='e'
dp[2] = dp[1] = 5
dp = [5, 5, 5]
Complete match! Window from 5 to 8: "bdde" (length 4)
Same length as "bcde", but starts later. We keep "bcde".

Final Answer: "bcde"

Visualization


def min_window(s1, s2):
    m, n = len(s1), len(s2)
    dp = [-1] * n
    result = ""
    min_len = float('inf')
    
    for i in range(m):
        for j in range(n - 1, -1, -1):
            if s1[i] == s2[j]:
                if j == 0:
                    dp[j] = i
                else:
                    dp[j] = dp[j - 1]
            
        if dp[n - 1] != -1:
            start = dp[n - 1]
            length = i - start + 1
            if length < min_len:
                min_len = length
                result = s1[start:i + 1]
    
    return result

Finding the shortest substring containing s2 as a subsequence

0 / 46

DP solution tracking start indices

Solution

The solution iterates through s1 once. For each character, we check all positions in s2 (in reverse order) to update our DP array. Whenever the last entry dp[n-1] becomes valid, we've found a complete subsequence and can check if it's the shortest so far.

Test Your Knowledge

Complexity Analysis

Time Complexity: O(m × n) where m is the length of s1 and n is the length of s2. For each character in s1, we potentially update all n entries in the dp array.

Space Complexity: O(n) We use a 1D DP array of size n (length of s2).

Alternative Approaches

Two Pointers with Expansion: Find each occurrence of s2 as a subsequence, then try to shrink from the left. Same time complexity but with higher constants.
2D DP: Use dp[i][j] to track starting positions for each (i, j) pair. Uses O(m × n) space but might be conceptually clearer for some.

The 1D DP approach we use is space-optimal while maintaining the same time complexity.

Purchase Premium to Access

This article is only available to Premium users.

Purchase Premium

The best mocks on the market.

Now up to 25% off

Learn More

Reading Progress

On This Page

Explanation

Starting Simple: The Brute Force Approach

A Smarter Approach: Forward Then Backward

The Key Observation

Why Dynamic Programming?

Why Iterate Backwards Through s2?

Walkthrough Example

Visualization

Solution

Alternative Approaches

Dynamic Programming

Minimum Window Subsequence

DESCRIPTION (credit Leetcode.com)

Explanation

Starting Simple: The Brute Force Approach

A Smarter Approach: Forward Then Backward

The Key Observation

Why Dynamic Programming?

Why Iterate Backwards Through s2?

Walkthrough Example

Visualization

Solution

Test Your Knowledge

Complexity Analysis

Alternative Approaches

Purchase Premium to Access

This article is only available to Premium users.

The best mocks on the market.

Questions

Learn

Links

Legal

Contact