# 0727. Minimum Window Subsequence

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

## Description

Given strings `s1` and `s2`, return *the minimum contiguous substring part of* `s1`*, so that* `s2` *is a subsequence of the part*.

If there is no such window in `s1` that covers all characters in `s2`, return the empty string `""`. If there are multiple such minimum-length windows, return the one with the **left-most starting index**.

**Example 1:**

```
**Input:** s1 = "abcdebdde", s2 = "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 s2 in the window must occur in order.
```

**Example 2:**

```
**Input:** s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
**Output:** ""
```

**Constraints:**

* `1 <= s1.length <= 2 * 104`
* `1 <= s2.length <= 100`
* `s1` and `s2` consist of lowercase English letters.

## ac

```java
class Solution {
    public String minWindow(String S, String T) {
        // edge cases
        if (S == null || S.length() == 0 || T == null || T.length() == 0 || S.length() < T.length())
            return "";

        int slen = S.length(), tlen = T.length();
        int[][] dp = new int[tlen+1][slen+1];  // dp[i][j] means start index of substring in 
        // init 1st row
        for (int c = 0; c < dp[0].length; c++) {
            dp[0][c] = c+1;
        }

        for (int r = 1; r < dp.length; r++) {
            for (int c = 1; c < dp[0].length; c++) {
                if (T.charAt(r-1) == S.charAt(c-1)) {
                    dp[r][c] = dp[r-1][c-1];
                } else {
                    dp[r][c] = dp[r][c-1];
                }
            }
        }

        // iterate last row, get result
        int min = Integer.MAX_VALUE, start = 0;
        for (int c = 1; c < dp[0].length; c++) {
            int len = c - dp[tlen][c] + 1;
            if (dp[tlen][c] != 0 && len < min) { // find shorter length, update
                start = dp[tlen][c]-1;
                min = len;
            }
        }

        // result
        return min == Integer.MAX_VALUE ? "" : S.substring(start, start+min);
    }
}
```

this version is more intuitive:

```java
class Solution {
    public String minWindow(String S, String T) {
        // edge cases
        if (S == null || S.length() == 0 || T == null || T.length() == 0 || S.length() < T.length())
            return "";

        int slen = S.length(), tlen = T.length();
        int[][] dp = new int[tlen][slen];  // dp[i][j] means start index of substring in 
        // init 1st row
        // for (int c = 0; c < slen; c++) {
        //     if (T.charAt(0) == S.charAt(c)) dp[0][c] = c;
        // }

        for (int r = 0; r < tlen; r++) {
            for (int c = 0; c < slen; c++) {
                if (T.charAt(r) == S.charAt(c)) {
                    dp[r][c] = r == 0 ? c : c == 0 ? -1 : dp[r-1][c-1];
                } else {
                    dp[r][c] = c == 0 ? -1 : dp[r][c-1];
                }
            }
        }

        // iterate last row, get result
        int min = Integer.MAX_VALUE, start = 0;
        for (int c = 0; c < slen; c++) {
            int len = c - dp[tlen-1][c] + 1;
            if (dp[tlen-1][c] != -1 && len < min) { // find shorter length, update
                start = dp[tlen-1][c];
                min = len;
            }
        }

        // result
        return min == Integer.MAX_VALUE ? "" : S.substring(start, start+min);
    }
}
```