# Python 20 lines AC O(n) solution

• Idea is pretty simple, keep two pointers left and right.

If s[left:right] has all chars in T, calculate distance and keep answer, then move left pointer.

If s[left:right] doesn't have all chars in T, move right pointer.

``````class Solution:
# @param {string} s
# @param {string} t
# @return {string}
# sliding window problem
# count all chars in string T
# left pointer point to string which has been processed
# right pointer point to string, which has not been processed
# 1.if all window from left to right contains all string T(counter values all less then or equal to 0)
#   calculate min window length, and keep answer
#   then move left pointer
# 2.else there are missing string in current answer
#   move right pointer
#   update counter
# repeat 1, 2 steps until right is equal to len(s), then break it
def minWindow(self, s, t):
left, right = 0, 0
# count T chars
counter = collections.defaultdict(int)
for a in t:
counter[a] += 1

minwindow = len(s) + 1

while right <= len(s):
# check all chars in T are in the current answer
if all(map(lambda x: True if x<=0 else False, counter.values())):
if minwindow > right-left:
minwindow = right-left
char = s[left]
if char in counter:
counter[char] += 1
left += 1
else:
if right == len(s):
break
char = s[right]
if char in counter:
counter[char] -= 1
right += 1

• I think this is not O(n) since ' all(map(lambda x: True if x<=0 else False, counter.values())):' takes len(counter) steps.

• answer = s[left:right] takes O(right - left) time. So it is better to keep index instead of string slice

• I used your idea and implement an O(n) solution

``````import sys
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
required, min_len = [0] * 128, sys.maxint
# record numbers of each character in t
for ch in t:
required[ord(ch)] += 1
left = right = min_start = 0
# count: number of characters that are still required
count = len(required) - required.count(0)
while right < len(s):
while count > 0 and right < len(s):
# move right till s[left : right] has all characters in t
required[ord(s[right])] -= 1
if required[ord(s[right])] == 0:
count -= 1
right += 1
# s[left : right] has all characters in t, move left pointer
while count == 0:
required[ord(s[left])] += 1
if required[ord(s[left])] == 1:
# now s[left : right] misses one character, update min_len if necessary
count = 1
if right - left < min_len:
min_len, min_start = right - left, left
left += 1

return s[min_start : min_start+min_len] if min_len != sys.maxint else ''
``````

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