Sources: leetcode 76

Rating: hard

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

- Solve without using a sort library.
- Sort in single-pass algorithm using constant space.

def minWindow(s: str, t: str) -> str:
# return the minimum window in s which contains all characters in t

**Solution**

First handle, the edge case of **s** being too short to contain **t**. Next use a dictionary **d** to figure out the counts of the letters in **t**, and a counter **missing** to determine how many letters must be included.

def minWindow(s, t):
if len(s) < len(t):
return ''
d = {}
for c in t:
if c not in d:
d[c] = 0
d[c] += 1
missing = len(t)
# return the minimum window in s which contains all characters in t

Next, set up index trackers **l** and **r** to manage the sliding window, with **L** and **R** as the final result to be used, updated as missing letters are found.

def minWindow(s, t):
if len(s) < len(t):
return ''
d = {}
for c in t:
if c not in d:
d[c] = 0
d[c] += 1
missing = len(t)
l = L = R = 0
for r, c in enumerate(s, 1):
if c in d and d[c] > 0:
missing -= 1
if c in d:
d[c] -= 1
while l < r and not missing:
if not R or r - l < R - L:
L, R = l, r
if s[l] not in d:
l += 1
else:
d[s[l]] += 1
if d[s[l]] > 0:
missing += 1
l += 1
# return the minimum window in s which contains all characters in t

Once the **L** and **R** limits are known, the substring is simply the subset of **s**.

**Final Code**

def minWindow(s, t):
if len(s) < len(t):
return ''
d = {}
for c in t:
if c not in d:
d[c] = 0
d[c] += 1
missing = len(t)
l = L = R = 0
for r, c in enumerate(s, 1):
if c in d and d[c] > 0:
missing -= 1
if c in d:
d[c] -= 1
while l < r and not missing:
if not R or r - l < R - L:
L, R = l, r
if s[l] not in d:
l += 1
else:
d[s[l]] += 1
if d[s[l]] > 0:
missing += 1
l += 1
return s[L:R]

### Like this:

Like Loading...

*Related*