Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Minimum Window Subsequence

LeetCode #727Hard

Smallest window of S containing T as a subsequence

Given strings S and T, return the shortest contiguous substring of S that contains T as a subsequence. If there are several such windows of minimum length, return the one starting at the smallest index; if none exists, return an empty string.

Asked atAmazonGoogle

Grid DP · carry the start index

time O(n·m)space O(n·m)

step 1 / 35

rows = S prefix length (0..9), cols = T prefix length (0..3) · value = window START index in S

Grid DP · carry the start index


▸
1dp[(n+1) × (m+1)], −1 = no window
2dp[i][0] = i            // empty T → start = i
3for i in 1..n: for j in 1..m:
4    if S[i−1] == T[j−1]: dp[i][j] = dp[i−1][j−1]   // diagonal
5    else:                dp[i][j] = dp[i−1][j]     // carry from above
6    if dp[i][m] valid: window = S[dp[i][m]..i)
7       keep it if shorter than best
8return best window

state

Sabcdebdde
Tbde
statedp[i][j] = window start in S

line 1Find the SMALLEST window of S = "abcdebdde" that contains T = "bde" as a subsequence (same order, gaps allowed). STATE: dp[i][j] = the START index in S of the smallest window of S[0..i) that already contains T[0..j). The clever part is that we carry that start index forward as the window grows.