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

dp[i][j]紀錄的是S中的starting index使得T[0...j-1]是S[0...i-1]的subsequence。dp table初始化為-1，代表沒有匹配到，然後初始化第一個column為該row的index。

// Dynamic Programming
// Can use an example to help derive transition state relation
// E.g. S = "dbd", T = "bd"
string minWindow(string S, string T) { // time: O(m * n); space: O(m * n)
    int m = S.size(), n = T.size(), start = -1, min_len = INT_MAX;
    // Padding one row and one column
    // dp[i][j] records the starting index in S s.t. T[0...j - 1] is a subsequence of S[0...i - 1]
    vector<vector<int> > dp(m + 1, vector<int> (n + 1, -1)); 
    // Initialize the first col in dp table
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;
    }
    // DP loop
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // DP state transition:
            // dp[i][j] = dp[i - 1][j - 1] if S[i - 1] == T[j - 1]
            // dp[i][j] = dp[i - 1][j] if S[i - 1] != T[j - 1]
            dp[i][j] = (S[i - 1] == T[j - 1]) ? dp[i - 1][j - 1] : dp[i - 1][j];
        }
        // Found possible substring
        if (dp[i][n] != -1) {
            int len = i - dp[i][n];
            if (len < min_len) {
                min_len = len;
                start = dp[i][n];
            }
        }
    }
    return (start != -1) ? S.substr(start, min_len) : ""; 
}

這個雙指針的方法算是改良過的暴力解。兩個pointers先正向搜尋直到找到完整匹配的，然後再反向往前搜尋，找到第一個匹配的前一個位置。可以處理掉中間連續相同的字元減少計算。

// Optimized Brute Force with Two Pointers
string minWindow(string S, string T) { // time: O(m * n); space: O(1)
    int m = S.length(), n = T.length(), start = -1, minLen = INT_MAX, i = 0, j = 0;
    while (i < m) {
        if (S[i] == T[j]) {
            if (++j == n) {
                int end = i + 1;
                while (--j >= 0) {
                    while (S[i--] != T[j]);
                }
                ++i, ++j;
                if (end - i < minLen) {
                    minLen = end - i;
                    start = i;
                }
            }
        }
        ++i;
    }
    return (start != -1) ? S.substr(start, minLen) : "";
}