Minimum Window Substring

Given two strings, original and check, return the minimum substring of original such that each character in check, including duplicates, are included in this substring. By "minimum", I mean the shortest substring. If two substrings that satisfy the condition have the same length, the one that comes lexicographically first is smaller.

Parameters

• original: The original string.
• check: The string to check if a window contains it.

Result

• The smallest substring of original that satisfies the condition.

Examples

Example 1

Input: original = "cdbaebaecd", check = "abc"

Output: baec

Explanation: The shortest valid windows are cdba and baec (both length 4). We return baec because when lengths tie, we pick the lexicographically smaller substring.

Constraints

• 1 <= len(check), len(original) <= 10^5
• original and check both contain only uppercase and lowercase characters in English. The characters are case sensitive.

Try it yourself

Solution