# Minimum Window Substring

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]
```