727. Minimum Window Subsequence

"cnhczmccqouqadqtmjjzl" "mm"

Version #1 O(MN) DP
Definition of DP is very tricky, but once you know it, the question became very straightforward
-> dp[s][t] -> start index to match S.substring(0, s) with T.substring(0, t) -> -1 if can't match

class Solution {
    public String minWindow(String S, String T) {
String result = null;
// dp[i][j] -> start index if want to match S.substring[0, i) with T.substring[0, j)
int[][] dp = new int[S.length() + 1][T.length() + 1];
for (int i = 0; i <= S.length(); i++) {
for (int j = 0; j <= T.length(); j++) {
if (i == 0 || j == 0) {
dp[i][j] = -1;
continue;
}
if (S.charAt(i - 1) == T.charAt(j - 1)) {
if (j - 1 == 0) {
dp[i][j] = i - 1;
} else {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
dp[i][j] = dp[i - 1][j];
}
if (j == T.length() && dp[i][j] != -1
&& (result == null || i - dp[i][j] < result.length())) {
result = S.substring(dp[i][j], i);
}
}
}
return result == null ? "" : result;
}
}