Leetcode 727: Minimum Window Subsequence

https://leetcode.com/problems/minimum-window-subsequence/

Notes:

This question can be viewed as a follow up to Leetcode 76

The basic idea is to scan string s to match string t.

(1): when s[i] == t[j], both i and j update; otherwise, only i updates;

(2): when j == t.size(), meaning it is matched. Then we need to check back what is the minimum substring that fits the requirement.

(3): the method is scan back starting with position s[i]. Step(2) guarantees that T is subsequence of S[start ... i] ending with S[i], so we just need to do the reverse as the in Step (1). Once j is back to 0, meaning that it is found, then we can update the length.

(4): the update the i to i+1 (please note that i right now is already scanned back in Step 3.)

(5): repeat the above step util S is all scanned.

See the code below:

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size(), 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;//the above while loop runs 1 more backwards for both i and j
                    if (end - i < minLen) {
                        minLen = end - i;
                        start = i;
                    }
                }
            }
            ++i;
        }
        return (start != -1) ? S.substr(start, minLen) : "";
    }
};

There is another way to do it by applying dp:

dp[i][j] represents the initial position in S that S(dp[i][j], ... i) contains T as a subsequence.

The state transfer equation:

dp[i][j] = dp[i-1][j-1] when S[i] == T[j]
= dp[i-1][j] when S[i] != T[j]

If(dp[i][n] != -1) means there is fit. Then update the length.

See the code below:

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;//initialization
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                dp[i][j] = (S[i - 1] == T[j - 1]) ? dp[i - 1][j - 1] : dp[i - 1][j];
            }
            if (dp[i][n] != -1) {
                int len = i - dp[i][n];
                if (minLen > len) {
                    minLen = len;
                    start = dp[i][n];
                }
            }
        }
        return (start != -1) ? S.substr(start, minLen) : "";
    }
};