**Minimum Window Substring**

#### Description

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

.

#### Example

1 | Input: S = "ADOBECODEBANC", T = "ABC" |

Note:

If there is no such window in`S`

that covers all characters in`T`

, return the empty string`""`

.

If there is such window, you are guaranteed that there will always be only one unique minimum window in`S`

.

#### Solution

At first, I want to use the same thought as I used in a similar probelm before (leetcode #30 - Substring with Concatenation of All Words). But then I realized these two are different, the window size of #30 is fixed, but this one is unknown. This problem is a kind of sliding window problem. We can keep two pointers, every time we only move one pointer and keep the other one still. In this case, the most important thing is to know when to increase the left pointer and right pointer.

Think about it in this way, if the current window contains all the elements in `T`

, then we can move the left pointer as much as possible until it is invalid again, while we could update the `minLength`

if it is smaller than `minLength`

. Otherwise, the current window does not contains all elements in `T`

, we can increase the right pointer untile the current window is valid. (*This is also useful for other sliding window problems.*)

Yeah~ We have solved one problem.

Another one is how to know the current window has all elements in `T`

? The official solution of this problem on leetcode uses two dictionaries (hashmap), which I think is a little bit messy and confused. So I looked at the discussion, (you know, I have been impressed by the discussion part for many times, I still got a lot to learn.) 哎呀说废话了。 Here is the solution. First, we need a dictionary to know the frequency of characters in `T`

, use a `count`

to record the number of current required elements. When `s[right] in d`

, we need to update `d[s[right]] -= 1`

, when `d[s[right]] >= 0`

, we know we can increase count by 1, so update `count += 1`

. If `count == len(T)`

, we know we have all elments in current window, then we could increase the left pointer to check the minLength and the current window. The detailed can be found in the algorithm (similar as right).

#### Algorithm

*Python*

```
def minWindow(self, s, t):
if not s or not t:
return ''
strLen, d = len(t), {}
for x in t:
d[x] = d.get(x, 0) + 1 # the frequency of every element in T
count, minLength = 0, float('inf')
i, j, head = 0, 0, 0
while j < len(s):
if s[j] in d:
d[s[j]] -= 1
if d.get(s[j], 0) >= 0: # if d[s[j]] < 0, it means there are some repeated characters in the window
count += 1
while count == strLen: # the current window is valid
if j - i + 1 < minLength: # if the length of current window is smaller than minLength
minLength = j - i + 1
head = i # head is to record the start index of minimum window
if s[i] in d: # this is the left side
d[s[i]] = d.get(s[i], 0) + 1
if d[s[i]] > 0: # only when d[s[i]] > 0, we know it is gonna be invalid
count -= 1
i += 1
j += 1
if minLength == float('inf'):
return ''
return s[head: head + minLength]
```

#### Complexity

- Time Complexity:
`O(|S| + |T|)`

- Space Complexity:
`O(|T|)`

# As we only use one dict