Straightforward Java DP solution with explanation.


  • 0
    S

    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 "";
            }
        }
    }
    

Log in to reply
 

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