Facebook Pixel

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: baec is the shortest substring of original that contains all of a, b, and c.

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

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro