Solution: Minimum Window Subsequence
Let's solve the Minimum Window Subsequence problem using the Sliding Window pattern.
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.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach would be to generate all possible substrings of str1
and then check which substrings contain str2
as a subsequence. Out of all the substrings in str1
that contain str2
as a subsequence, we’ll choose the one with the shortest length. Now, let’s look at the cost of this solution. We need two nested loops to get all possible substrings and another loop to check whether each substring contains all the required characters. This brings the time complexity to . Since we’re not using any extra space, the space complexity is .
Optimized approach using sliding window
To eliminate the extra traversals of the substrings, we use the sliding window approach. With this approach, we only consider the substrings that we are sure contain all the characters of str2
in the same order. This problem can be conveniently solved using the sliding window pattern. The idea is to keep track of whether the subsequence has been found or not and to select the shortest subsequence from str1
.
Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.
Step-by-step construction
The first step of the solution is to initialize the variables. We begin by creating two variables, sizeStr1
and sizeStr2
, to store the lengths of str1
and str2
, respectively. We then initialize minSubLen
to infinity, which will be used to store the length of the minimum subsequence.
To help us traverse the two strings, we create two indexes, indexS1
and indexS2
, which initially point to the first characters of str1
and str2
, respectively. These indexes will be incremented as we scan through the strings to find the subsequence.
Finally, we initialize minSubsequence
to an empty string. This variable will store the output, which is the smallest possible subsequence.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.