# Python dp + binary search

• O(T*S*log(S))

``````from collections import defaultdict
from bisect import bisect_left
class Solution:
def minWindow(self, S, T):
indices = defaultdict(list)
for i in range(len(S)):
indices[S[i]].append(i)

dp = defaultdict(lambda: defaultdict(lambda: -1))

ret = (len(S), len(S))
for t in range(0, len(T)):
for s in range(0, len(S)):
if T[t] == S[s]:
if t == 0:
dp[t][s] = s
else:
ids = indices[T[t-1]]
pos = bisect_left(ids, s) - 1
if pos >= 0:
dp[t][s] = dp[t-1][ids[pos]]
if dp[t][s] != -1 and t == len(T)-1:
ret = min(ret, (s+1 - dp[t][s], dp[t][s]))
l, s = ret
return S[s:s+l]
``````

Another solution which is O(T*S) but apparently not fast enough

``````class Solution:
def minWindow(self, S, T):
dp = []
for i in range(len(T)):
dp.append([])
for j in range(len(S)):
dp[-1].append(-1)

ret = (len(S), len(S))
for t in range(0, len(T)):
for s in range(0, len(S)):
if T[t] == S[s]:
if t == 0:
dp[t][s] = s
elif t>0 and s>0:
dp[t][s] = dp[t-1][s-1]

if t == len(T)-1 and dp[t][s] != -1 :
ret = min(ret, (s+1 - dp[t][s], dp[t][s]))
elif s>0:
dp[t][s] = dp[t][s-1]
l, s = ret
return S[s:s+l]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.