727. Minimum Window Subsequence

https://leetcode.com/problems/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].

给定S和T, 问S中包含以T为subseq的最小substr是什么。argmin + substr=>滑动窗口 or DP。和常见的string match问题类似，dp[i][j]存以i为底的最短的S的substr能匹配T[:j]的长度。分为S[i]和T[j]是否相等两种情况。最后再遍历找以不同S[i] dp[i][N]的最小值为全局最优，用底减去长度为对应的substr。

class Solution:
    def minWindow(self, S: str, T: str) -> str:
        M, N, res = len(S), len(T), ''
        dp = [[math.inf] * (M + 1) for _ in range(N + 1)]
        for i in range(1, N + 1):
            for j in range(1, M + 1):
                if T[i - 1] == S[j - 1]:
                    dp[i][j] = 1 if i == 1 else dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = dp[i][j - 1] + 1 
        mi = min(dp[-1])
        if mi == math.inf: return ''
        for i in range(1, M + 1):
            if dp[-1][i] == mi:
                return S[i - mi: i]

class Solution {
public:
    string minWindow(string S, string T) {
        const int M = S.size(), N = T.size();
        vector<vector<int>> dp(M + 1, vector<int>(N + 1, -1));
        for (int i = 0; i <= M; ++i) dp[i][0] = i;
        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];
            }
        }
        int res = M;
        pair<int, int> r;
        for (int i = N; i <= M; ++i) {
            const int len = i - dp[i][N]; 
            if (len < res) {
                res = len;
                r.first = dp[i][N];
                r.second = len;
            }
        }
        return S.substr(r.first, r.second);
    }
};