Minimum Window Subsequence

February 7, 2024

Problem Statement #

Given two strings s1 and s2, return the minimum window in s1 which will contain all the characters in s2 in the order they appear in s2. 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.

Solution Approach #

The solution involves a two-pointer technique to explore all the substrings of s1 that could potentially cover s2 and then narrowing down to the one with minimum length that satisfies the condition.

Algorithm Steps #

1. Initialize two pointers: start to iterate through s1 and match to iterate through s2.
2. Use a sliding window on s1 to find a substring that contains s2.
3. Once a valid window is found, attempt to minimize it until it no longer contains s2.
4. Keep track of the minimum length and starting index of such a window.
5. Return the minimum window from s1 after traversing the entire string.

Code (Python) #

def minWindowSubsequence(s1, s2):
    minWindow = ""
    minLen = float("inf")
    start = 0

    while start < len(s1):
        match = 0
        for i in range(start, len(s1)):
            if s1[i] == s2[match]:
                match += 1
                if match == len(s2):
                    end = i
                    while match > 0:
                        if s1[i] == s2[match - 1]:
                            match -= 1
                        i -= 1
                    i += 1
                    if end - i + 1 < minLen:
                        minLen = end - i + 1
                        minWindow = s1[i:end + 1]
                    start = i + 1
                    break
        else:
            break

    return minWindow

# Example usage
print(minWindowSubsequence("abcdebdde", "bde"))  # Output: "bcde"

Time Complexity #

• The time complexity is O(n*m), where n is the length of s1 and m is the length of s2, because, in the worst case, we might need to scan s1 for each character in s2.

Space Complexity #

• The space complexity is O(1), assuming the output string does not count towards the space complexity, as we only use a few variables for tracking purposes.