Minimum Window Substring

Try to solve the Minimum Window Substring problem.

We'll cover the following

Statement#

Given two strings, s and t, find the minimum window substring in s, which has the following properties:

  1. It is the shortest substring of s that includes all of the characters present in t.

  2. It must contain at least the same frequency of each character as in t.

  3. The order of the characters does not matter here.

Note: If there are multiple valid minimum window substrings, return any one of them.

Constraints:

  • Strings s and t consist of uppercase and lowercase English characters.

  • 1 ≤\leq s.length, t.length ≤103\leq 10^3

Examples#

Created with Fabric.js 3.6.6 Input t A B C A C B Sample example 1 Output s A B A A C B B A

1 of 3

Created with Fabric.js 3.6.6 B A C A Output s A C B B A C A Input Sample example 2 t A B A

2 of 3

Created with Fabric.js 3.6.6 Input t A B C C s A B A A C B A B Sample example 3 Output No substring of t is present in s, so an empty string is returned.

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check that you’re solving the correct problem.

Minimum Window Substring

1

What is the output if the following strings are given as input?

s = “cabwefgewcwaefgcf”

t = “cae”

A)

“cwae”

B)

“cabwe”

C)

“aefgc”

D)

“”

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Set up a sliding, adjustable window to move across the string s.

Initialize two collections: one to store the frequency of characters in t and the other to track the frequency of characters in the current window.

Iterate over s, expanding the current window until the frequencies of characters of t in the window are at least equal to their respective frequencies in t.

Trim the window by removing all the unnecessary characters. If the current window size is less than the length of the minimum window substring found so far, update the minimum window substring.

Continue iterating over s and perform the previous two steps in each iteration.

Return the minimum window substring.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Input #2
Minimum Window Substring

Solution: Minimum Window Subsequence

Solution: Minimum Window Substring