Minimum Window Subsequence

Photo by William Daigneault on Unsplash

Given strings s1 and 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.

Example 1:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: 
"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.

Example 2:

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""

Constraints:

• 1 <= s1.length <= 2 * 104
• 1 <= s2.length <= 100
• s1 and s2 consist of lowercase English letters.

Solution

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 a in 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:

1. Traverse the s1 string, and for each letter, check if it’s equal to the current letter in s2.
2. If the letters are equal, move to the next letter in both the strings.
3. When the last letter of s2 is matched with a letter of s1, mark that letter position of s1 as a possible window.
4. Now, go backward from the end of s1 and match the letters with s2 from the marked position. Do this until the s1 string is exhausted.
5. Check if your current window is smaller than the previous one. If yes, mark it as the minimum window.
6. Repeat from step 2 until you reach the end of s1.

Let’s look at the code for the solution below:

Time complexity

The time complexity will be O(S×T).

Space complexity

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

https://www.linkedin.com/in/jaydeep-shil-75a90847