214. Minimum Window Substring

Given strings s and t, return the minimum window substring of s that contains all characters of t (including duplicates). If no such window exists, return the empty string. If multiple windows tie on length, return the leftmost. Input: '"s", "t"'.

Input: '"s", "t"'.

Output: Quoted string — minimum window or empty.

Examples

Input: "ADOBECODEBANC", "ABC"
Output: "BANC"
Explanation: Smallest window containing A,B,C.

Input: "a", "a"
Output: "a"
Explanation: Whole string.

Input: "a", "aa"
Output: ""
Explanation: Not enough a's.

Constraints

• 1<=s.length<=10^5
• 1<=t.length<=10^5

Asked by