# Python accepted queue solution, O(ST)

• The idea is to keep a queue of existing matches, the element of the queue is a pair of 2 numbers, first one being the start index in S, and second being matched chars in T.

For cases like S = 'ffffffffeeeeeaaa' and T = 'ffea', O(ST) is guaranteed by keep popping previous pairs if there are worse than later ones. Worse, meaning it has a earlier start(1st number in pair) and same match(2nd number in pair)

``````class Solution:
def minWindow(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
ret = ''
exists = collections.deque()
for i, c in enumerate(S):
for exist in exists:
if T[exist[1]] == c:
exist[1] += 1
if c == T[0]:
exists.append([i, 1])

while len(exists) > 1 and exists[0][1] == exists[1][1]:
exists.popleft()
if exists and exists[0][1] == len(T):
if not ret or i - exists[0][0] + 1 < len(ret):
ret = S[exists[0][0]:i+1]
exists.popleft()
while exists and ret and i - exists[0][0] + 1 > len(ret):
exists.popleft()

return ret

``````

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