LC 727

Description

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input: 
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.

Note:

• All the strings in the input will only contain lowercase letters.
• The length of S will be in the range [1, 20000].
• The length of T will be in the range [1, 100].

Solution

Use dynamic programming to solve the problem.

Use dp[i][j] to represent the largest starting index of the valid substring of S, where T has length i and S has length j. So if S[j] == T[i], then update the index, dp[i][j] = dp[i - 1][j - 1], else cannot update the index, dp[i][j] = dp[i][j - 1].

Finally, go through the last row to find the substring with min length and appears first.

Time complexity is O(s.len * t.len), space complexity is O(s.len * t.len).

class Solution {
    // dynamic programming
    // time O(s.len * t.len), space O(s.len * t.len)
    public String minWindow(String S, String T) {
        // check border cases
        if (S == null || T == null || S.length() == 0 || T.length() == 0 || S.length() < T.length()) {
            return "";
        }
        
        int m = S.length();
        int n = T.length();
        int[][] dp = new int[m][n]; // store the largest index of valid substring until the pos
        
        for (int i = 0; i < m; i++) {
            if (S.charAt(i) == T.charAt(0)) {
                dp[i][0] = i;
            } else {
                if (i == 0) {
                    dp[i][0] = -1;
                } else {
                    dp[i][0] = dp[i - 1][0];
                }
            }
        }
        
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (i < j) {
                    dp[i][j] = -1; // if s.length < t.length, s cannot contain any valid substring
                    continue;
                }
                
                if (S.charAt(i) == T.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j]; // nothing to update
                }
            }
        } // end of for j
        
        int len = Integer.MAX_VALUE; // length of substring
        int start = 0; // start index of substring
        
        for (int i = 0; i < m; i++) {
            if (dp[i][n - 1] != -1 && i - dp[i][n - 1] + 1 < len) {
                len = i - dp[i][n - 1] + 1;
                start = dp[i][n - 1];
            }
        }
        
        return len == Integer.MAX_VALUE ? "" : S.substring(start, start + len);
    }
}