Is Minimum Window Subsequence easy or hard?

Minimum Window Subsequence is classified as a hard problem on LeetCode. The challenge comes from combining subsequence matching with window minimization and avoiding repeated scans of the string. Dynamic programming is typically required to reach optimal complexity.

Minimum Window Subsequence Python/Java solution

Most implementations follow the same dynamic programming structure regardless of language. Create a 2D DP array, iterate through S and T to update subsequence start indices, and track the minimum window whenever a full match of T is completed. The logic translates directly to Python, Java, C++, Go, and TypeScript.

How to solve Minimum Window Subsequence in O(n * m)?

Use dynamic programming to track where each partial subsequence begins. Maintain dp[i][j] representing the starting index in S where the first j characters of T form a subsequence ending at i. When the final column (matching all of T) is reached, compute the window length and update the best answer.

What is the best approach for Minimum Window Subsequence?

The most reliable approach uses dynamic programming. Build a DP table that tracks the starting index of subsequences matching prefixes of T while scanning S. This avoids repeatedly rescanning the string and finds the smallest valid window in O(n * m) time and O(n * m) space.

Is Minimum Window Subsequence asked at Google/Amazon/Meta?

Minimum Window Subsequence appears in interview preparation lists for companies like Google, Amazon, and Meta because it combines subsequence matching with dynamic programming and window reasoning. It is considered a strong test of advanced string manipulation skills.

What data structure is used in Minimum Window Subsequence?

The primary structure is a dynamic programming table that tracks subsequence start indices. The algorithm also relies on sequential string traversal and index tracking rather than complex data structures like heaps or trees.

What is the time complexity of Minimum Window Subsequence?

The optimal dynamic programming solution runs in O(n * m) time, where n is the length of S and m is the length of T. Each pair of indices is processed once while updating subsequence start positions. Space complexity is also O(n * m) for the DP table.

Description Hints 1 Solution Video 19:10

727. Minimum Window Subsequence

Hard43.5% acceptance5 companiesPremium elsewhere, free here

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 * 10⁴
1 <= s2.length <= 100
s1 and s2 consist of lowercase English letters.

Asked at 5 companies

eBay Salesforce Airbnb

Google Meta

Topics

Hints open one at a time

Hint 1

Let dp[j][e] = s be the largest index for which S[s:e+1] has T[:j] as a substring.

19:10

Still stuck?Read the written solution, or watch a walkthrough.

Open solution