727. Minimum Window Subsequence

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].

------------------------
Solution #1, 指针
找到一个匹配之后，以结尾为起始点，倒退着往前找。这样找到的是在[i, j]里最短的符合要求的substring。最坏结果是找到跟原来一摸一样的。
O(m * n) time. 对Complexity的需要研究一下

ref： https://leetcode.com/problems/minimum-window-subsequence/discuss/109356/JAVA-two-pointer-solution-(12ms-beat-100)-with-explaination

class Solution {
    public String minWindow(String s, String t) {
        int si = 0, ti = 0;
        String rt = s + "123";
        while (si < s.length()) {
            if (s.charAt(si) == t.charAt(ti)) {
                if (ti == t.length() - 1) {
                    int end = si;                    
                    while (ti >= 0) {
                        while (s.charAt(si) != t.charAt(ti)) {
                            si--;
                        }
                        ti--;
                        si--;
                    }
                    
                    si++;
                    if (rt.length() > end - si + 1) {
                        rt = s.substring(si, end + 1);
                    }
                }
                ti++;
            }
            
            si++;
        }
        
        return rt.equals(s + "123") ? "" : rt;
    }
}

Solution #2, DP
dp[i][j] = k, i为T的index，j为S的index，k为以[0,i]，[0,j]这2段substring最小的起点在s上
如果s[j] == t[i], dp[i][j]那可以借用dp[i - 1][j - 1]时的起点
如果s[j] ！= t[i]，可以借用dp[i][j - 1]

注意dp的初始赋值

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == t.charAt(0)) dp[0][i] = i;
            else if (i > 0) dp[0][i] = dp[0][i - 1];
            else dp[0][i] = -1;
        }

        for (int i = 1; i < m; i++) {
            dp[i][0] = -1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1 ; j < n; j++) {
                if (i > j) dp[i][j] = -1;
                else {
                    if (t.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
        }

        int min = n;
        String rt = "";
        for (int i = 0; i < n; i++) {
            if (dp[m - 1][i] == -1) continue;
            if (min > i - dp[m - 1][i] + 1) {
                rt = s.substring(dp[m - 1][i], i + 1);
                min = i - dp[m - 1][i] + 1;
            }
        }

        return rt;
    }
}