# Python O(n) solution, 164ms

• Two steps:

1. Find the first minimum window that covers all letters in T, with `start` and `end` points to the starting and ending point of the minimum window;

2. Discard the letter x at `start` and advance to the next letter if it's in T, advance `end` until it points to the same discarded letter x

Note: during step 1 and 2, advancing pointers may come to letters that are in T, use hash table `extra` to keep track of these letters. When the discarded letter is in `extra`, a window is found without advancing the `end` pointer.

String `S` is only traversed once, so the time complexity is O(n), two hash tables `to_find` and `extra` have space O(m).

``````def minWindow(self, S, T):
letters = set(T)
ls = len(S)

# find the first substring that works
first_match = self.first_match(S, T)
if not first_match:
return ''
else:
start, end, extra = first_match
min_window = (end - start, start, end)

# traverse the string and update start and end
while start < end < ls:

# move start on to the next letter
while start < end:
start += 1
if S[start] in letters:
break

# if discarded letter has extra, no need update end
min_window = min(min_window, (end - start, start, end))
continue

# otherwise move end until it points to the discarded letter
while end < ls:
end += 1
if end == ls:
continue

letter = S[end]
min_window = min(min_window, (end - start, start, end))
break

if letter in letters:
extra[letter] += 1

_, start, end = min_window
return S[start: end + 1]

def first_match(self, S, T):
letters = set(T)
to_find = collections.defaultdict(lambda: 0)
extra = collections.defaultdict(lambda: 0)

# build hash table
for i in T:
to_find[i] += 1

# find the start position
for index, letter in enumerate(S):
if letter in to_find:
start = index
break
else:
return False

# find the end position
for index, letter in enumerate(S[start:], start):
if letter not in letters:
continue
if letter in to_find:
to_find[letter] -= 1
if to_find[letter] == 0:
to_find.pop(letter)
else:
extra[letter] += 1
if not to_find:
end = index
break
else:
return False
return start, end, extra``````

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