Given two strings, str1 and str2, return the smallest substring of str1 that contains every character from str2 (including duplicates). If no such substring exists, return an empty string.
A substring is any contiguous sequence of characters within a string. For example, the substrings of string abc are a, b, c, ab, bc, and abc. A substring is formed by selecting a starting and ending point without skipping characters in between.
Input
str1: A string
str2: A string
Notes
If multiple solutions exist, you may return any of them
Examples
Input: str1 = "ABCD", str2 = "AC"
Output: "ABC"
Explanation: The substring 'ABC' contains both 'A' and 'C'
Input: str1 = "AAABBBCCC", str2 = "ABC"
Output: "ABBBC"
Explanation: The substring 'ABBBC' contains 'A', 'B', and 'C', making it the smallest valid substring.
Input: str1 = "A", str2 = "AA"
Output: ""
Explanation: str1 does not have enough 'A's to match the two required in str2, so the result is an empty string.
Constraints
1 <= str1.length, str2.length <= 10,000
str1 and str2 contains only uppercase English letters