Skip to main content

727. Minimum Window Subsequence

hard

Find the shortest substring of s1 such that t is a subsequence of that substring. 2D DP tracks the start index of the best matching window ending at each (i, j) — close cousin of Edit Distance.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= s1.length <= 2 * 10^4
  • 1 <= s2.length <= 100
  • s1 and s2 consist of lowercase English letters.

Examples

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
""

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = the largest starting index in s1 such that s2[0..j-1] is a subsequence of s1[startIndex..i-1] ending at i.

Hint 2

If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (extend the match by one char).

Hint 3

Else: dp[i][j] = dp[i-1][j] (we may skip s1[i-1] without consuming s2).

Hint 4

Base: dp[i][0] = i. After the table is filled, scan j = len(s2) row to find the (start, end) pair with the smallest end - start + 1.

Solution approach

Reveal approach

Bottom-up 2D DP. m = len(s1), n = len(s2). dp[i][j] stores the largest start index k in s1 such that s2[0..j-1] is a subsequence of s1[k..i-1]. Initialize dp[i][0] = i for every i (empty s2 matches a window that starts at i — zero-width). Set dp[0][j>0] = 0 (impossible). Recurrence: if s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1]; else dp[i][j] = dp[i-1][j]. After filling, the minimum window is over i = 1..m: where dp[i][n] != 0, the window is s1[dp[i][n] - 1 .. i - 1] inclusive. Track the smallest length and tiebreak by the smallest start. Return that substring, or '' if none. Time O(m * n), space optimizable to O(n) with care.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • string-dp
  • sliding-window

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Minimum Window Subsequence and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →