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 1:

Input: S = "abcdebdde", T = "bde"Output: "bcde"Explanation: "bcde" is the answer because it occurs before "bdde" which has the same length."deb" is not a smaller window because the elements of T in the window must occur in order.

 

1 class Solution { 2 public: 3     string minWindow(string s, string t) { 4         int ns = s.size(), nt= t.size(); 5         int dp[ns+1][nt+1] = {}; 6         const int mxx = ns + 1; 7         //for(int i=0;i<=ns;i++) dp[i][0]=i; 8          9         for (int i = 0 ; i <= ns; ++i) {10             for (int j = 1; j <= nt; ++j) {11                 dp[i][j] = mxx;12                 if (i) {13                     dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]);14                     if (s[i-1] == t[j-1]) dp[i][j]  = min(dp[i][j], 1 + dp[i-1][j-1]);15                 }16             }17         }18         19         int ans = ns + 1, x = -1;20         for (int i = 0; i <=ns; ++i) 21             if (dp[i][nt] < ans) {22             x = i;23             ans = dp[i][nt];24         }25         26         if (x < 0) return "";27         return s.substr(x-ans,ans);28     }29 };