# Straightforward Java DP solution with explanation.

• Define f(i, j) as the min length of a sub string that ends at S[i] that has sub string {T[0]..T[j]} as a sub sequence. The recursion equation is f(i, j) = f(i-1, j-1) + 1, when S[i] = T[j], and f(i, j) = f(i-1, j) + 1 when S[i] != T[j]. Then the min length of the sliding window is the min of all f(i, n). Here is a straightforward DP implementation with O(mn) space based on this idea.

class Solution {
public String minWindow(String S, String T) {
int m = S.length();
int n = T.length();
// dp[i][j] is the min length of the substring that ends at S[i-1] that covers substring T[0..j-1]
int[][] dp = new int[m+1][n+1];
for(int i = 0; i <= m; i++) {
// a string with 0 length covers an empty string
dp[i][0] = 0;
}
for(int j = 1; j <= n; j++) {
// a string with 0 lengths cannot cover any string that is not zero length
dp[0][j] = -1;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(S.charAt(i-1) == T.charAt(j-1)) {
if(dp[i - 1][j - 1] == -1) {
dp[i][j] = -1;
}
else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
else {
if(dp[i - 1][j] == -1) {
dp[i][j] = -1;
}
else {
dp[i][j] = dp[i - 1][j] + 1;
}
}
}
}
int min = Integer.MAX_VALUE;
int end = -1;
for(int i = 1; i <= m; i++) {
if(dp[i][n] != -1 && dp[i][n] < min) {
min = dp[i][n];
end = i;
}
}
if(min != Integer.MAX_VALUE) {
return S.substring(end - min, end);
}
else {
return "";
}
}
}

Here is a more concise implementation with O(n) space.

class Solution {
public String minWindow(String S, String T) {
int m = S.length();
int n = T.length();
int[] dp = new int[n+1];
for(int j = 1; j <= n; j++) {
// a string with 0 length cannot cover any string that is not zero length
dp[j] = -1;
}
int min = Integer.MAX_VALUE;
int end = -1;
for(int i = 1; i <= m; i++) {
// work backwards
for(int j = n; j >= 1; j--) {
if(S.charAt(i-1) == T.charAt(j-1)) {
if(dp[j - 1] == -1) {
dp[j] = -1;
}
else {
dp[j] = dp[j - 1] + 1;
}
}
else if(dp[j] != -1){
dp[j] = dp[j] + 1;
}
}
if(dp[n] != -1 && dp[n] < min) {
min = dp[n];
end = i;
}
}

if(min != Integer.MAX_VALUE) {
return S.substring(end - min, end);
}
else {
return "";
}
}
}

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