This is a dynamic programming solution

scan from left to right. At each step (say position i that where S[i] is in T)

- we want to find shortest interval that ends in i and includes all

letters in T - we can do this by scanning from right (i) to left but that takes O(n) time and makes algorithm O(n^2). in order to make this constant time we keep 2 data structures:

rpos: a sorted list of positions where rightmost positions of characters of T in S are kept

r: a dictionary mapping from a character to the position. values of r is same as rpos

```
def minWindow(self, S, T):
res, rpos, r, Tcount = "",[], collections.defaultdict(list), collections.Counter(T)
for i,c in filter(lambda x: x[1] in T,enumerate(S)): #go only over chrs exist in T
if len(r[c]) == Tcount[c]: #reached limit. so we need to remove
rpos.remove(r[c].pop(0))
r[c].append(i) #add to dict
rpos.append(i) #add to array
if len(rpos) == len(T) and (res=="" or rpos[-1]-rpos[0]<len(res)):
res = S[rpos[0]:rpos[-1]+1]
return res
```