Best runtime is 112ms (beats 100% of python submissions)

idea:

go through the string, record the positions of the characters we want to find. Whenever we find all the characters, keep updating the start position to find a substring with local minimum length. After this, update the start position to next one and then keep looking for the missing character.

Implentation:

use a dictionary `d`

to store the number of each character we need to find. (negative values mean we have some extra!) `ToFind`

is the total number of characters we still need to find. `ind`

is a list of indices of the characters in `d`

. `head`

is a pointer in `ind`

so `ind[head]`

is the start position of the substring and `s[ind[head]]`

is that character).

Nore: I use a small trick to initialize `L`

, and `R`

, the start and end position of the minimum window substring. (Their initial values have properties that `R - L = len(s)`

and `s[L:R+1]=""`

. Therefore, when we find the first window with indices p and q , q - p must be smaller than R - L so we can update L and R. if we cannot find any window to update L and R, it would return an empty string. )

```
def minWindow(self, s, t):
d = {}
for c in t:
d[c] = d.get(c,0) + 1
ToFind, ind = len(t), []
L, R, head = -len(s)-1, -1, 0
for i, c in enumerate(s):
if c in d:
ind.append(i)
d[c] -= 1
if d[c] >=0:
ToFind -= 1
if ToFind == 0:
while d[s[ind[head]]] < 0: # s[ind[head]] is the character
d[s[ind[head]]] += 1
head += 1
if i - ind[head] < R - L:
L, R = ind[head], i
d[s[ind[head]]] += 1
ToFind += 1
head += 1
return s[L:R+1]
```