Leetcode 727. Minimum Window Subsequence

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]

Analysis:
This is a two-sequence DP problem. We define dp[S.length() + 1][T.length() + 1], where dp[i][j] means the START POSITION of the minimum windows subsequnce for the first i charactgers from S and first j characters from T.

Code (Java):

class Solution {
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return "";
        }
        
        int[][] dp = new int[S.length() + 1][T.length() + 1];
        for (int i = 1; i <= T.length(); i++) {
            dp[0][i] = -1;
        }
        
        for (int i = 1; i <= S.length(); i++) {
            dp[i][0] = i;
        }
        
        int minLen = Integer.MAX_VALUE;
        int startPos = -1;
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                dp[i][j] = -1;
                
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            
            if (dp[i][T.length()] != -1) {
                int len = i - dp[i][T.length()];
                if (len < minLen) {
                    startPos = dp[i][T.length()];
                    minLen = len;
                }
            }
        }
        
        return startPos == -1? "" : S.substring(startPos, startPos + minLen);
    }
}