# Minimum Window Subsequence

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:

Example 2:

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.

Full Stack Programmer, love to solve problem’s during free time.

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.