#192HardSliding Window· Minimum Window with Multiset Coverage

Shortest Excerpt Covering All Letters

A crossword setter has a long text `text` and a bag of required letters `needed` (letters may repeat, for example `"aab"` requires two a's and one b). She wants the **shortest contiguous excerpt** of the text that contains at least as many copies of each required letter as the bag asks for. Extra letters in the excerpt are allowed. Return that excerpt. If several excerpts have the same shortest length, return the one that starts earliest in the text. If no excerpt works, return the empty string.

Input format

`text` and `needed`: strings of English letters (uppercase and lowercase are different letters).

Output format

The shortest (leftmost on ties) substring of `text` covering all letters of `needed` with multiplicity, or an empty string.

Examples

Input: text = "ADOBECODEBANC", needed = "ABC"

Output: "BANC"

The excerpt "BANC" is the shortest piece of the text that contains an A, a B and a C.

Input: text = "aab", needed = "aab"

Output: "aab"

The whole text is needed because it must contain two a's and one b.

Input: text = "ab", needed = "abc"

Output: ""

The text has no c, so no excerpt can cover the required letters and the answer is empty.

Constraints

1 <= text.length <= 10^5
1 <= needed.length <= 10^5
Both strings contain only English letters (a-z, A-Z).

#sliding-window
#hash-table
#strings
#two-pointers