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.