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

• b'
\n\n

#### Approach #1: Dynamic Programming (Postfix Variation) [Accepted]

\n

Intuition

\n

Let\'s work on a simpler problem: `T = \'abc\'`. Whenever `S[k] = \'c\'`, the most recent window `[i, j]` before it (that contains `\'ab\'`) becomes the window `[i, k]`.

\n

Here, a window is the best possible window that ends at a given index, which ensures every window considered has increasing starting and ending indices.

\n

For example, if `S = \'aacbbc\'`, then after considering `T = \'ab\'`, the windows are `[[1, 3], [1, 4]]`, and after parsing `\'c\'`, the windows are `[[1, 5]]`.

\n

As we iterate through `k` for `S[k] = T[2]`, we could just remember the last window seen. This leads to a dynamic programming solution.

\n

Algorithm

\n

As we iterate through `T[j]`, let\'s maintain `cur[e] = s` as the largest index such that `T[:j]` is a subsequence of `S[s: e+1]`, (or `-1` if impossible.) Now we want to find `new`, the largest indexes for `T[:j+1]`.

\n

To update our knowledge as `j += 1`, if `S[i] == T[j]`, then `last` (the largest `s` we have seen so far) represents a new valid window `[s, i]`.

\n

In Python, we use `cur` and `new`, while in Java we use `dp[j]` and `dp[~j]` to keep track of the last two rows of our dynamic programming.

\n

At the end, we look at all the windows we have and choose the best.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where are the lengths of `S, T`. We have two for-loops.

\n
• \n
• \n

Space Complexity: , the length of `dp`.

\n
• \n
\n
\n

#### Approach #2: Dynamic Programming (Next Array Variation) [Accepted]

\n

Intuition

\n

Let\'s guess that the minimum window will start at `S[i]`. We can assume that `S[i] = T[0]`. Then, we should find the next occurrence of `T[1]` in `S[i+1:]`, say at `S[j]`. Then, we should find the next occurrence of `T[2]` in `S[j+1:]`, and so on.

\n

Finding the next occurrence can be precomputed in linear time so that each guess becomes work.

\n

Algorithm

\n

We can precompute (for each `i` and `letter`), `next[i][letter]`: the index of the first occurrence of `letter` in `S[i:]`, or `-1` if it is not found.

\n

Then, we\'ll maintain a set of minimum windows for `T[:j]` as `j` increases. At the end, we\'ll take the best minimum window.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where are the lengths of `S, T`, and assuming a fixed-sized alphabet. The precomputation of `nxt` is , and the other work happens in two for-loops.

\n
• \n
• \n

Space Complexity: , the size of `windows`.

\n
• \n
\n
\n

Analysis written by: @awice. Approach #1 inspired by @zestypanda.

\n
'