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].Intuition
\nLet\'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
\nAs 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\nComplexity Analysis
\nTime Complexity: , where are the lengths of S, T. We have two for-loops.
Space Complexity: , the length of dp.
Intuition
\nLet\'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.
\nAlgorithm
\nWe 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
\nTime 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.
Space Complexity: , the size of windows.
Analysis written by: @awice. Approach #1 inspired by @zestypanda.
\n