This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:**

`S`

will be in the range `[1, 20000]`

.`T`

will be in the range `[1, 100]`

.b'

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

\n

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

\n

\n

'
\n\n

\n**Intuition**

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

.

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.

\nFor 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]]`

.

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.

**Algorithm**

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

.

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

.

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.

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

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: , where are the lengths of

\n`S, T`

. We have two for-loops. \n - \n
Space Complexity: , the length of

\n`dp`

. \n

\n

**Intuition**

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.

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

\n**Algorithm**

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.

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.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where are the lengths of

\n`S, T`

, and assuming a fixed-sized alphabet. The precomputation of`nxt`

is , and the other work happens in two for-loops. \n - \n
Space Complexity: , the size of

\n`windows`

. \n

\n

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

\n