# My code's complexity seems linear, just move two pointers, why always exceed time limit in the len(s)=100000 case?

• ``````import sys
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
if len(s) == 0 or len(t) == 0 or len(t) > len(s):
return ""
start = 0
end = 0
current_start = 0
current_end = 0
current_length = sys.maxint
get = {letter:0 for letter in set(t)}
want = {letter:t.count(letter) for letter in set(t)}
left = set(t)
# print len(s),len(t)
i = 0
while end < len(s):
# print i,end
# print start,end,current_start, current_end
# print len(left)
while end < len(s):
if s[end] in set(t):
get[s[end]] += 1
if get[s[end]] >= want[s[end]] and s[end] in left:
left.remove(s[end])
if len(left) == 0:
end += 1
break
end += 1
if end == len(s) and len(left)!=0:
break
while start < end:
# print s[start],start
if s[start] in set(t):
get[s[start]] -= 1
if get[s[start]]<want[s[start]]:
start += 1
break
start += 1
if end-start < current_length:
current_length = end - start + 1
current_start = start -1
current_end = end

return s[current_start:current_end]``````

• Are you sure it's solely `n=len(s)` that's the problem?

For example bulding `want` from `k=len(t)` is an `k^2` operation.

Also there are many `set(t)`s in your code, maybe you need to create it once, not every iteration. Your main loop runtime just because `set(t)`s is: `2*n*k`.

Also how long does `in set(t)` take (not counting construction of `set(t)`)? Make sure that all `add`/`remove`/`in`/`[]` operations are `O(1)`.

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