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
= “”
str2
= “”
In this example, “” is a substring of str1
, from which we can derive str2
simply by deleting both the instances of the character . 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, “”.
If there is no substring in
str1
that covers all characters instr2
, 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:
-
str1.length
-
str2.length
str1
andstr2
consist of uppercase and lowercase English letters.
Examples
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy