Minimum Window Subsequence

Try to solve the Minimum Window Subsequence problem.

We'll cover the following

Statement#

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

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:

  • 11 ≤\leq str1.length ≤\leq 2×1032 \times 10^3
  • 11 ≤\leq str2.length ≤\leq 100100
  • str1 and str2 consist of uppercase and lowercase English letters.

Examples#

Created with Fabric.js 3.6.6 Input str2 "bde" The strings "bcde" and "bdde" are both minimumsubsequences, but "bcde" occurs before "bdde".The substring “deb” is the shortest to contain all therequired characters, but they do not appear in therequired order. str1 "abcdebdde" Output String "bcde" Output Sample example 1

1 of 2

Created with Fabric.js 3.6.6 str1 "abcdebdde" Output str2 "bdf" Output String "" Input Sample example 2 str1 does not contain character "f" that's why an empty string is returned.

2 of 2

Understand the problem#

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

Minimum Window Subsequence

1

What are valid substrings of “Educative”?

A)

“tive”

B)

“ude”

C)

“cat”

D)

“vit”

Question 1 of 50 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.

Begin iterating through str1 to locate a potential window that contains all the characters of str2 in their order of appearance.

Once you’ve identified a potential end, backtrack through the characters of str1 from this end position until you’ve found all the characters of str2 in reverse order. This helps locate the potential start of the smallest subsequence.

Update the minimum window subsequence if the current window is smaller than the shortest subsequence found so far.

Repeat the process, starting every time from the second character of the current window, until the end of str1 has been reached.

Return the minimum window subsequence.

Try it yourself#

Implement your solution in main.py in the following coding playground:

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

Solution: Find Maximum in Sliding Window

Solution: Minimum Window Subsequence