DP C++ solution with detailed explanation - good for beginners

• The pattern of this problem is similar to a DP state problem. Here the states are:`S[k] : Matched characters till index k in T`.The dp variable holds the length of sequence matched in the current state. At each step of dp we loop through all characters in T checking for a match, if we dont match a character we increment the dp count, if we do match we take the result from index k-1 at previous step and increment

An example should hopefully things more clear Suppose S : `t1xxt2xt1t3t2t3` && T: `t1t2t3`

dp[t1] dp[t2] dp[t3]
t1 1 0 0
x 2 0 0
x 3 0 0
t2 3 4 0
x 4 5 0
t1 1 6 0
t3 2 7 7
t2 3 3 0
t3 4 4 4

Hence the answer is 4 ending at index corresponding to last t3. There is a subtle point which makes the dp solution work which is : if we reach some intermediate state k at step i it is going to better or equivalent to current state k(ie youngest to reach is better). This is easy to see for the first character, but requires for some thinking for others. Imagine we have `t1xxxt2xxt2` the second t2 is equivalent to t2 at this point wrt to the dp. Another example is `t1xxxt2t1t2` - here we can see that the last t2 is actually optimal since it is reached by taking a newer t1. This is why the `dp[i][j] = dp[i-1][j-1]+1` equation works and we don't need to check the edge from `dp[i-1][j]` (ie the old value) when reaching state j.

``````class Solution {
public:
string minWindow(string S, string T) {
int s = S.size();
int t = T.size();
vector<vector<int>> dp(s,vector<int> (t,-1));
string res;
int min_d=INT_MAX;

for (int i=0; i < s; ++i) {
for (int j=0;j<t;++j) {
if (S[i]==T[j]) {
if (j == 0) dp[i][j] =1;
else if (i != 0 && dp[i-1][j-1] != -1) dp[i][j] = dp[i-1][j-1]+1;
} else if (i != 0 && dp[i-1][j] != -1) {
dp[i][j] = dp[i-1][j] +1;
}

if (j == t-1 && dp[i][j] > 0 && dp[i][j] < min_d) {
min_d = dp[i][j];
res = S.substr(i-min_d+1,min_d);
}
}
}

return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.