Minimum Window Subsequence

Given two strings, str1 and str2, find the shortest substring in str1 such that str2 is a subsequence of that substring.

Statement

A substring is defined as a contiguous sequence of characters within a string. A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Let's say you have the following two strings:

str1 = "abbcbabbcb" str2 = "acac"

In this example, "abbcabbc" is a substring of str1, from which we can derive str2 simply by deleting both the instances of the character bb. Therefore, str2 is a subsequence of this substring. Since this substring is the shortest among all the substrings in which str2 is present as a subsequence, the function should return this substring, that is, "abbcabbc".

If there is no substring in str1 that covers all characters in str2, return an empty string.

If there are multiple minimum-length substrings that meet the subsequence requirement, return the one with the left-most starting index.

Constraints

• 1 ≤ str1.length ≤ 2×10³
• 1 ≤ str2.length ≤ 100
• str1 and str2 consist of uppercase and lowercase English letters.

Examples

Sample Example 1

Input:

• str1 = "abcdebdde"
• str2 = "bde"

Output String: "bcde"

Explanation: The strings "bcde" and "bdde" are both minimum-length substrings, but "bcde" occurs before "bdde". The substring "deb" is the shortest to contain all the required characters, but they do not appear in the required order.

Sample Example 2

Input:

• str1 = "abcdebdde"
• str2 = "bdf"

Output String: ""

Explanation: str1 does not contain the character "f", that's why an empty string is returned.