Minimum Window Substring

Hard

Given two strings s and t, return the smallest substring of s that contains every character of t (including duplicates). If there is no such window, return the empty string "". When several windows share the minimum length, return the one with the smallest starting index.

Example 1

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2

Input:  s = "a", t = "a"
Output: "a"

Example 3

Input:  s = "a", t = "aa"
Output: ""

Constraints

• 1 <= s.length <= 16
• 1 <= t.length <= 6
• s and t consist of lowercase and uppercase English letters.