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