Minimum Window Substring

Return the smallest substring of s that contains every character of t (with multiplicity: t = "aab" needs two as and one b). If there are several of the same smallest length, return the leftmost. If there is none, return "".

For s = "ADOBECODEBANC" and t = "ABC" the answer is "BANC".

The starter code checks windows from every start. It is correct but too slow for long strings.

Examples

Example 1

Input:

min_window('ADOBECODEBANC', 'ABC')

Output:

'BANC'

Example 2

Input:

min_window('a', 'aa')

Output:

''

Constraints

• 0 <= len(s) <= 200000
• 0 <= len(t) <= 100000
• Letters (upper or lower case); an empty t gives "".