DIY: Minimum Window Substring

Solve the interview question "Minimum Window Substring" in this lesson.

Problem statement

Suppose you are given two strings, say S and T. You have to find the smallest window substring of T. The smallest window substring is the shortest sequence of characters in S that includes all of the characters present in T with the same frequency.

Input

The input will be a string of characters.

# Example 1

S = "ABAACBBA" 
T = "ABC"

# Example 2

S = "ABAACBAB" 
T = "ABCC"

Output

The output will either contain a string of characters or an empty string.

# Example 1

"ACB"

# Example 2 

""

Coding exercise

You have to implement the minWindow function that takes two strings, S and T, and returns the minimum window substring of S, such that every character of T (including duplicates) is also present in the sequence. The sequence of the characters does not matter. If there is no such substring, you return an empty string.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.