# minimum window subsequence leetcode dynamic programming solution

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.

Solution:

Concept is almost inspired from $O(N log N)$ solution for longest increasing sequence in a integer array presented here. Let DP[i] represent longest increasing sequence in T which matches [0:i] subsequence of S. So,

DP[j] = i if S[j] == T[i] and j == 0

DP[j] = DP[j-1] if S[j] == T[i]


And then we are looking for DP[len(T)-1].

class Solution:
def minWindow(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
dp = [-1] * (len(T)+1)
dic = {}
for i, t in enumerate(T):
dic.setdefault(t, []).append(i)
global_index, starting_index, global_count = -1, -1, 1 << 31
for i in range(len(S)):
if S[i] in dic:
for j in dic[S[i]][::-1]:
if j == 0:
dp[j] = i
else:
dp[j] = dp[j-1]
if dp[len(T)-1] != -1 and (i - dp[len(T)-1] + 1) < global_count:
starting_index, global_count = dp[len(T)-1], i - dp[len(T)-1] + 1
if starting_index == -1:
return ""
return S[starting_index:starting_index + global_count]