727. Minimum Window Subsequence

这道题跟76. Minimum Window Substring不一样，那个题是找anagram，不需要保持顺序，这个需要
O(mn) time O(mn) space
把S的每个字符的位置按顺序记录在对应的T的每个字符的bucket里，因为S里的子序列必须严格follow T的顺序所以T的每个bucket对应的下标必须严格递增，扫描所有的bucket将不合法的下标排除，每次扫完更新全局结果即可

class Solution {
public:
    string minWindow(string S, string T) {
        unordered_map<char, vector<int>> c2q;
        int m = S.length(), n = T.length();
        for (int i = 0; i < n; ++i) {
            c2q[T[i]].push_back(i);
        }
        vector<queue<int>> q(n);
        for (int i = 0; i < m; ++i) {
            if (c2q.count(S[i])) {
                for (int j : c2q[S[i]]) {
                    q[j].push(i);
                }
            }
        }
        if (q[0].empty()) return "";
        int l = -1, r = m;
        while (!q[0].empty()) {
            for (int i = 1; i < n; ++i) {
                while (!q[i].empty() && q[i - 1].front() >= q[i].front()) {
                    q[i].pop();
                }
                if (q[i].empty()) return l == -1 ? "" : S.substr(l, r + 1 - l); // 如果有任何一个bucket空了，说明S里不存在合法的子序列或者之前已找到的子序列已经最优
            }
            if (q[n - 1].front() - q[0].front() < r - l) {
                l = q[0].front();
                r = q[n - 1].front();
            }
            q[0].pop();
        }
        return S.substr(l, r + 1 - l);
    }
};

双指针 O(mn) time O(1) space
先正着扫找符合要求的子序列，再倒着扫找到最短的子序列，类似sliding window

class Solution {
public:
    string minWindow(string S, string T) {
        int b = -1, len = INT_MAX;
        for (int m = size(S), n = size(T), i = 0, j = 0; i < m;) {
            while (i < m && j < n) { // 正向在S里找到第一个包含T序列的子串
                if (S[i] == T[j]) ++j;
                ++i;
            }
            if (j == n) { // 如果找到
                int e = i; // 先记录当前尾下标
                --i; --j; // 回退两个指针
                while (i >= 0 && j >= 0) { // 倒着在当前子串里找最大的起始下标
                    if (S[i] == T[j]) --j;
                    --i;
                }
                ++i; ++j; // 修正指针得到最大起始下标
                if (e - i < len) { // 更新结果
                    len = e - i;
                    b = i;
                }
                ++i; // 别忘了找到了一个可能结果还要往前移动指针继续找
            }
        }
        return b == -1 ? "" : S.substr(b, len);
    }
};

dp O(mn) time O(mn) space
f[i][j]表示S的前i个字符里包括T的前j个字符的子序列的最大的起始下标
需要维护一个全局最小起始下标和全局最小子序列长度
如果S[i - 1] == T[j - 1]则f[i][j]直接继承f[i - 1][j - 1]否则f[i][j]继承f[i - 1][j]即S的前i - 2个字符里包括T的前j个字符的子序列的最大的起始下标

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.length(), n = T.length(), mn = m, b = -1;
        vector<vector<int>> f(m + 1, vector<int>(n + 1, -1));
        for (int i = 0; i <= m; ++i) { // S的前i个字符和T的前0个字符空串的最大起始下标即为i这样f[i][0] - i为0，即不存在这样的子序列
            f[i][0] = i;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                f[i][j] = S[i - 1] == T[j - 1] ? f[i - 1][j - 1] : f[i - 1][j];
            }
            if (f[i][n] != -1) { // 如果S的前i个字符包括整个T则进行更新
                if (i - f[i][n] < mn) {
                    mn = i - f[i][n];
                    b = f[i][n];
                }
            }
        }
        return b == -1 ? "" : S.substr(b, mn);
    }
};

dp O(mn) time O(n) space

class Solution {
public:
    string minWindow(string S, string T) {
        int m = S.length(), n = T.length(), mn = m, b = -1;
        vector<int> f(n + 1, -1);
        f[0] = 0;
        for (int i = 1; i <= m; ++i) {
            vector<int> t(n + 1, -1);
            t[0] = i;
            for (int j = 1; j <= min(i, n); ++j) {
                t[j] = S[i - 1] == T[j - 1] ? f[j - 1] : f[j];
            }
            t.swap(f);
            if (f[n] != -1) {
                if (i - f[n] < mn) {
                    mn = i - f[n];
                    b = f[n];
                }
            }
        }
        return b == -1 ? "" : S.substr(b, mn);
    }
};