# A different O(n) approach - 9 lines

• 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))
if len(rpos) == len(T) and (res=="" or rpos[-1]-rpos[0]<len(res)):
res = S[rpos[0]:rpos[-1]+1]
return res``````

• Too concise to understand for me. Anyone can explain it a bit more and even better write this approach in Java? I don't know Python.

• I think the OJ has no implementation of the templates for collections, or not?

• no, many packages including 'collections' are imported by OJ

• This isn't O(n) but O(n2) for three reasons:

• Every `r[c].pop(0)` is only O(n).
• Every `rpos.remove(...)` is only O(n).
• Every `res = S[rpos[0]:rpos[-1]+1]` is only O(n).

``````def minWindow(self, S, T):
cost1 = cost2 = cost3 = 0
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))
cost1 += len(r[c])
cost2 += len(rpos)
For example for input `S = "A" * 201` and `T = "A" * 101`, the costs are `10000 10000 10201`.