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



给定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。

```python
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]
```

```cpp
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);
    }
};

```
