> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/727-minimum-window-subsequence.md).

# 727     Minimum Window Subsequence

## 727. [Minimum Window Subsequence](https://leetcode.com/problems/minimum-window-subsequence/description/)

## 1. Question

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

## 2. Implementation

**(1) DP**

思路: 建立二维数组dp， dp\[i]\[j]表示在s\[0...j]中包含子序列 t\[0...i]的s的起始地点, 比如s = 'abcde", t = "ade", 那么在dp\[2]\[4]的值是0,代表s包含子序列t的开始位置是0，也就是s中的a的位置。当dp填充完后，我们扫dp的最后一行(因为它代表了包含t的s起始位置这个信息), 如果dp\[i]\[j] 不为 -1，则包含t的subsequence的window size为 j - dp\[m]\[j] + 1, 如果这个值比我们当前的最短长度短，则更新start和当前最短长度minLen两个变量, 最后要求的解释s.substring(start, start + len)

```java
class Solution {
    public String minWindow(String S, String T) {
        int m = T.length(), n = S.length();
        int[][] dp = new int[m][n];

        for (int j = 0; j < n; j++) {
            dp[0][j] = T.charAt(0) == S.charAt(j) ? j : -1;
        }

        for (int i = 1; i < m; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 1; i < m; i++) {
            int startIndex = -1;
            for (int j = 0; j < n; j++) {
                if (startIndex != -1 && T.charAt(i) == S.charAt(j)) {
                    dp[i][j] = startIndex;
                }

                if (dp[i - 1][j] != -1) {
                    startIndex = dp[i - 1][j];
                }
            }
        }

        int minLen = n;
        int start = -1;

        for (int j = 0; j < n; j++) {
            if (dp[m - 1][j] != -1) {
                if (j - dp[m - 1][j] + 1 < minLen) {
                    start = dp[m - 1][j];
                    minLen = j - dp[m - 1][j] + 1;
                }
            }
        }
        return start == -1 ? "" : S.substring(start, start + minLen);
    }
}
```

## 3. Time & Space Complexity

**DP**: 时间复杂度O(mn), 空间复杂度O(mn)