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


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

    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.

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

    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.

    Complexity Analysis

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

    • Space Complexity: , the length of dp.

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

    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.

    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

    • 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.

    • Space Complexity: , the size of windows.

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

    Submit Solution