Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.
If there is no such window in S that covers all characters in T, return the empty string "".
If there are multiple such minimum-length windows, return the one with the left-most starting index.
Example - Input:
S = "abcdebdde", T = "bde"
Example - Output: "bcde"
I have spent approximately 2 hours on this problem with no progress. I just peeked at the "TAGS" of this problem and it says dynamic programming. I spent 2 hours trying two-pointers but could not solve it.
I am hoping you all can help me with the dynamic programming approach. I saw the space complexity was O(Length(S)*Length(T))
so this hints at 2D-DP array-table but I am unsure where the motivation of this even comes from and how to proceed further.
My possible DP ideas were
Boolean DP[i][j] ==> T[0, i] is a subsequence of S[0, j]
Boolean DP[i][j] ==> T[0, i] is a subsequence of S[0, j] AND T[i] == S[j]
None of these are correct/working. Please help me out!
Thanks
You can compute
LCS[i][j]
— longest common subsequence ofT[0..i)
andS[0..j)
. (i
andj
are excluded)Then, find minimum
j
such thatLCS[Length(T)][j] = Length(T)
.And, finally, go backwards to find the first symbol of substring:
P.S.: I forgot that you need minimum length... so, you need to check each
j
with "code and text" above to find minimum length, and then find thatj
.Hi there,
Thanks for the reply. I implemented this solution, but it is a slow solution.
Apparently there is a faster DP state for this than using LCS. Any ideas on how to approach that? I am unable to figure it out. Here is the actual problem: https://leetcode.com/problems/minimum-window-subsequence/description/
Thanks
dp[i][j] — minimum length of a substring of S which starts in i and has T[j..len(T) - 1] as a subsequence.
dp[i][j] = 0, if j = len(T)
dp[i][j] = ∞, if i ≥ len(S)
dp[i][j] = dp[i + 1][j] + 1, if S[i] ≠ T[j]
dp[i][j] = dp[i + 1][j + 1] + 1, otherwise.
The answer should be the minimum value of dp[i][0], for all i in [0, len(S) - 1].