Minimum Window Subsequence - Practice Coding Problems

Minimum Window Subsequence - Problem

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

If no such window exists in s1 that covers all characters of s2, return an empty string "".

If there are multiple such minimum-length windows, return the one with the leftmost starting index.

Note: A subsequence is a sequence that can be derived from another sequence by deleting some (not necessarily consecutive) elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: s1 = "adbec", s2 = "abc"

› Output: "adbec"

💡 Note: The minimum window substring "adbec" contains "abc" as a subsequence: a→d→b→e→c matches a→b→c by taking positions 0, 2, 4.

Example 2 — No Valid Window

$ Input: s1 = "adc", s2 = "abc"

› Output: ""

💡 Note: There is no subsequence "abc" in "adc" because 'b' is missing, so return empty string.

Example 3 — Multiple Windows

$ Input: s1 = "abacbcab", s2 = "abc"

› Output: "abc"

💡 Note: Multiple valid windows exist: "abacbc" and "abc". We return "abc" as it's shorter and leftmost among equal-length options.

Constraints

1 ≤ s1.length ≤ 2000
1 ≤ s2.length ≤ 100
s1 and s2 consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given s1 and target subsequence s2

Find Valid Windows

Identify all substrings containing s2 as subsequence

Return Minimum

Select shortest window, leftmost if tied

Key Takeaway

🎯 Key Insight: Use expand-contract sliding window technique to efficiently find minimum valid windows

Asked in

G Google 25 f Facebook 20 a Amazon 15 M Microsoft 12

The key insight is to use a sliding window approach with two phases: expand to find a valid window containing the subsequence, then contract to minimize it. Best approach uses two pointers with expand-contract cycles. Time: O(mn), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - 2D Table	O(mn)	O(mn)	Use 2D DP to track minimum window ending at each position
Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring of s1 to see if s2 is a subsequence
Optimized Sliding Window	O(mn)	O(1)	Use two pointers to expand and contract window efficiently

Dynamic Programming - 2D Table — Algorithm Steps

Step 1: Create DP table dp[len(s1)][len(s2)+1]
Step 2: Initialize base cases for empty s2
Step 3: Fill DP table using recurrence relation
Step 4: Track minimum window length across all valid endings

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP Table

Create m×n table with base cases

Fill Table

Use recurrence relation to fill entries

Extract Result

Find minimum from valid complete matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

char* solution(const char* s1, const char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    if (len1 == 0 || len2 == 0) {
        char* empty = malloc(1);
        empty[0] = '\0';
        return empty;
    }
    
    int** dp = malloc(len1 * sizeof(int*));
    for (int i = 0; i < len1; i++) {
        dp[i] = malloc((len2 + 1) * sizeof(int));
        for (int j = 0; j <= len2; j++) {
            dp[i][j] = INT_MAX;
        }
        dp[i][0] = 1; // Base case
    }
    
    int minLen = INT_MAX;
    int bestStart = -1, bestEnd = -1;
    
    for (int i = 0; i < len1; i++) {
        int maxJ = (i + 1 < len2) ? i + 1 : len2;
        for (int j = 1; j <= maxJ; j++) {
            if (s1[i] == s2[j - 1]) {
                if (j == 1) {
                    dp[i][j] = 1;
                } else if (i > 0) {
                    for (int k = 0; k < i; k++) {
                        if (dp[k][j - 1] != INT_MAX) {
                            int newLen = i - k + 1;
                            if (newLen < dp[i][j]) {
                                dp[i][j] = newLen;
                            }
                        }
                    }
                }
                
                if (j == len2 && dp[i][j] < minLen) {
                    minLen = dp[i][j];
                    bestStart = i - dp[i][j] + 1;
                    bestEnd = i;
                }
            } else if (i > 0) {
                if (dp[i - 1][j] != INT_MAX) {
                    dp[i][j] = dp[i - 1][j] + 1;
                }
            }
        }
    }
    
    // Cleanup
    for (int i = 0; i < len1; i++) {
        free(dp[i]);
    }
    free(dp);
    
    char* result = malloc(len1 + 1);
    if (bestStart == -1) {
        result[0] = '\0';
    } else {
        strncpy(result, s1 + bestStart, bestEnd - bestStart + 1);
        result[bestEnd - bestStart + 1] = '\0';
    }
    
    return result;
}

int main() {
    char s1[1001], s2[101];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    
    char* result = solution(s1, s2);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Fill DP table of size m×n where m=len(s1), n=len(s2)

✓ Linear Growth

Space Complexity

O(mn)

2D DP table stores m×n states

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

865 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - 2D Table — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler