Smallest Window With All Letters

Write min_window(text, need) that returns the shortest substring of text containing every character of need, counting repeats: if need has two as, the substring needs at least two as. A substring is a run of characters next to each other. If several shortest substrings exist, return the one that starts first. If none exists, return the empty string ''. Upper and lower case letters are different characters.

Examples

min_window('XAYBZCAB', 'ABC')   # returns 'CAB'
min_window('banana', 'aan')     # returns 'ana'
min_window('abc', 'abcd')       # returns ''

In the first example, 'AYBZC' and 'BZCA' also contain an A, a B and a C, but 'CAB' is shorter. In 'banana', 'nan' is as short as 'ana' but has only one a.

Constraints

• 0 <= len(text) <= 100,000
• 1 <= len(need) <= 100
• Both strings hold only letters and digits

Note

Checking every substring takes billions of steps for long texts. Aim for a number of steps that grows with the length of text.