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.

Note:

• All the strings in the input will only contain lowercase letters.

• The length of S will be in the range [1, 20000].

• The length of T will be in the range [1, 100].

 

class Solution {public:    string minWindow(string s, string t) {        int ns = s.size(), nt= t.size();        int dp[ns+1][nt+1] = {};        const int mxx = ns + 1;        for (int i = 0 ; i <= ns; ++i) {            for (int j = 1; j <= nt; ++j) {                dp[i][j] = mxx;                if (i) {                    dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]);                    if (s[i-1] == t[j-1]) dp[i][j]  = min(dp[i][j], 1 + dp[i-1][j-1]);                }            }        }                int ans = ns + 1, x = -1;        for (int i = 0; i <=ns; ++i) if (dp[i][nt] < ans) {            x = i;            ans = dp[i][nt];        }                if (x < 0) return "";        return s.substr(x-ans,ans);    }};