Help solving window substring problem

Revision en1, by aakarshmadhavan, 2018-06-27 05:06:57
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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aakarshmadhavan 2018-06-27 05:06:57 1147 Initial revision (published)