aakarshmadhavan's blog

Help solving window substring problem
By aakarshmadhavan, history, 6 years ago, In English 
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

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can compute LCS[i][j] — longest common subsequence of T[0..i) and S[0..j). (i and j are excluded)

Then, find minimum j such that LCS[Length(T)][j] = Length(T).

And, finally, go backwards to find the first symbol of substring:

for (int i = Length(T) - 1, k = j - 1; k >= 0 && i >= 0; --k)
    if (T[i] == S[k])
        --i;
if (i == -1)
    ++k, cout << S.substr(k, j - k); // Print the S[k..j)
else
    cout << "";

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 that j.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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].

      → Reply