# C++ DP O(len(S)*len(T))

• ``````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);
}
};
``````

• Hi @elastico thanks for sharing your solution. Could you please provide a brief explanation? I'm having a hard time following it, and unfortunately I don't get it. Thanks again, Clayton

• @claytonjwong
`f[i][j]` is the min length of `w` in `S[0,...i - 1]` (the first i char from S) that have subsequence `T[0, ..., j - 1]` (first j char from T). the statement `dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]);` is the hardest part of this solution, the `1` means the char `s[i - 1]` (the last char of first i chars) is added. if `S[i - 1] == T[j - 1]`, we update `f[i][j]`.
Taking this simple example:

``````i = 1 2 3 4 5 6
j---a b c d e a
1 b 6 1 2 3 4 5
2 d 6 6 6 3 4 5
3 e 6 6 6 6 4 5
``````

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