Minimum Window Subsequence
s2, return the minimum contiguous substring part of
s1, so that
s2 is a subsequence of the part.
If there is no such window in
s1 that covers all characters in
s2, return the empty string
"". If there are multiple such minimum-length windows, return the one with the left-most starting index.
Input: s1 = "abcdebdde", s2 = "bde"
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of s2 in the window must occur in order.
Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
1 <= s1.length <= 2 * 104
1 <= s2.length <= 100
s2consist of lowercase English letters.
Initially, we can search for the first occurrence of the subsequence. Then, we can find the subsequence in the opposite direction to find the smaller one. For example, if we have
s2= ab and
s1= acab, the first occurrence would result in
acab, and we’ll start searching in the opposite direction. When
b is matched, we’ll look for the most recent
s2, which will give us
ab as our final result. We can then apply this method to bigger strings as well.
The following illustration might clarify this process.
Let’s see how we might implement this functionality:
- Traverse the
s1string, and for each letter, check if it’s equal to the current letter in
- If the letters are equal, move to the next letter in both the strings.
- When the last letter of
s2is matched with a letter of
s1, mark that letter position of
s1as a possible window.
- Now, go backward from the end of
s1and match the letters with
s2from the marked position. Do this until the
s1string is exhausted.
- Check if your current window is smaller than the previous one. If yes, mark it as the minimum window.
- Repeat from step 2 until you reach the end of
Let’s look at the code for the solution below:
The time complexity will be O(S×T).
The space complexity will be O(1) because the program uses constant space.
If you like the content please follow me here @medium and at LinkedIn