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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →