Very brief explannation : m = len(T), n = len(S), scan string S and maintain a up to date list of start index of matching T in list dp(size of m), dp[i] denotes the start index when i+1 chars of T are matched. When T[i] appears in S, we simply update dp[i] = dp[i-1], when T[0] appears in S with index, we update dp[0] = index. Whenever dp[m-1] is updated, we have a new window that T is sub-sequence of, and we keep a running minimum of this window width

We scan S once, and each update depends the number of same char in T. The worst case is O(mn) when all position of T are identical. When the char in T doesn't have much repetition, O(n) time complexity is achieved.

Space complexity O(m)

```
class Solution(object):
def minWindow(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
n = len(S)
m = len(T)
dic = dict()
for i, s in enumerate(T):
dic.setdefault(s, []).append(i)
dp = [-1 for i in xrange(m)]
count = n+1
start = -1
for index, c in enumerate(S):
if c in dic:
for i in dic[c][::-1]:
if i == 0:
dp[i] = index
else:
dp[i] = dp[i-1]
if i == m-1 and dp[i] >= 0 and index - dp[i]+1 < count:
count = index - dp[i] + 1
start = dp[i]
if dp[-1] < 0:
return ""
return S[start:start+count]
```