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 forloops. 
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 fixedsized alphabet. The precomputation ofnxt
is , and the other work happens in two forloops. 
Space Complexity: , the size of
windows
.
Analysis written by: @awice. Approach #1 inspired by @zestypanda.