Minimum Window Subsequence - Solution & Explanation
Problem Statement
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 in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.
Example 1:
Input: s1 = "abcdebdde", s2 = "bde" Output: "bcde" Explanation: "bcde" is the answer because it occurs before "bdde" which has the same length. "deb" is not a smaller window because the elements of s2 in the window must occur in order.
Example 2:
Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u" Output: ""
Constraints:
1 <= s1.length <= 2 * 1041 <= s2.length <= 100s1ands2consist of lowercase English letters.
Approach Overview
Problem Overview: Given two strings S and T, find the smallest substring of S such that T appears inside it as a subsequence. Characters in T must appear in order but do not need to be contiguous. If multiple windows exist, return the one with the minimum length.
Approach 1: Brute Force Subsequence Check (O(n^2 * m) time, O(1) space)
Start a window at every index i in S. From that position, scan forward trying to match characters of T sequentially. If the full subsequence is found ending at position j, record the window S[i...j]. Repeat for all starting indices and keep the smallest valid window. This approach works because subsequence matching is straightforward: iterate through S while advancing a pointer in T when characters match. However, repeatedly rescanning the string makes the algorithm expensive for large inputs.
This method highlights the core requirement of subsequence matching, but its nested scanning leads to poor performance. It is mainly useful for understanding the problem constraints before optimizing with dynamic programming.
Approach 2: Dynamic Programming Window Tracking (O(n * m) time, O(n * m) space)
The optimized approach builds a DP table where dp[i][j] stores the starting index in S of a subsequence matching the first j characters of T and ending at position i. Iterate through S and update transitions based on whether S[i] matches T[j]. If characters match, inherit the start index from dp[i-1][j-1]; otherwise carry forward dp[i-1][j]. Whenever a full subsequence match for T is detected, compute the window length and update the best result.
The key insight: instead of restarting subsequence searches repeatedly, the DP table remembers where each partial match began. That converts repeated scans into constant-time lookups. The algorithm processes each pair of indices once, giving predictable O(n * m) time.
This technique relies heavily on string processing and sequence alignment patterns often seen in sliding window-style substring problems, though the window boundaries here are derived from DP states rather than two pointers.
Recommended for interviews: Interviewers typically expect the dynamic programming solution. Starting with the brute force explanation demonstrates that you understand subsequence matching, but the DP approach shows the ability to eliminate repeated scans and track partial matches efficiently. Discussing the transition rule and how the start index propagates through the table signals strong problem‑solving depth for hard string problems.
Solution
We define f[i][j] to represent the starting position of the shortest substring of the first i characters of string s1 that contains the first j characters of string s2. If it does not exist, it is 0.
We can derive the state transition equation:
$
f[i][j] = \begin{cases}
i, & j = 1 and s1[i-1] = s2[j] \
f[i - 1][j - 1], & j > 1 and s1[i-1] = s2[j-1] \
f[i - 1][j], & s1[i-1] \ne s2[j-1]
\end{cases}
Next, we only need to traverse s1. If f[i][n] \gt 0, update the starting position and length of the shortest substring. Finally, return the shortest substring.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of strings s1 and s2$, respectively.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Scan | O(n^2 * m) | O(1) | Conceptual baseline or when input size is very small |
| Dynamic Programming Window Tracking | O(n * m) | O(n * m) | General optimal solution for large strings and interview settings |
Video Solution
Minimum Window Subsequence | Leetcode 727 • Coding at a Scale • 24,865 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Window Subsequence easy or hard?
Minimum Window Subsequence Python/Java solution
How to solve Minimum Window Subsequence in O(n * m)?
What is the best approach for Minimum Window Subsequence?
Is Minimum Window Subsequence asked at Google/Amazon/Meta?
What data structure is used in Minimum Window Subsequence?
What is the time complexity of Minimum Window Subsequence?
Ready to solve this problem?
Practice Minimum Window Subsequence with our built-in code editor and test cases.
Practice on FleetCode