How do you find the minimum window substring that contains every character of a target string?
You keep two counts, one of what you need and one of what you have, and you shrink the window as soon as you have everything you need.
from collections import Counter
def min_window(s, t):
if not s or not t or len(t) > len(s):
return ""
need = Counter(t)
window = Counter()
missing = len(t)
best_start = 0
best_len = len(s) + 1
left = 0
for right, letter in enumerate(s):
if letter in need:
window[letter] += 1
if window[letter] == need[letter]:
missing -= 1
# The window has everything we need, so try to make it smaller.
while missing == 0:
length = right - left + 1
if length < best_len:
best_len = length
best_start = left
first = s[left]
if first in need:
window[first] -= 1
if window[first] < need[first]:
missing += 1
left += 1
if best_len == len(s) + 1:
return ""
return s[best_start:best_start + best_len]
So how does it work? The dictionary need says how many of each letter the target wants. The dictionary window says how many of each letter the current window holds. And the variable missing says how many of the letters you need are still not there.
Every time you add a letter to the window, you check whether that letter is now complete, and if it is then you reduce missing. While missing is zero the window is a valid answer, so you try to make it smaller by taking letters off the left, and you keep the smallest one that you find.
And the complexity is O of n for the time, because the right end only moves forwards and the left end only moves forwards, so each letter goes in and out of the window once.
The next two questions in this topic look at the impossible case and at returning more detail.