We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Window Subsequence

Number: 727

Difficulty: Hard

Paid? Yes

Companies: Meta, Microsoft, Google, eBay

Problem Description

Given two strings s1 and s2, the goal is to find the minimum contiguous substring of s1 such that s2 is a subsequence of that substring. In other words, all characters of s2 must appear in the substring in the same order, although not necessarily consecutively. If there is no such substring in s1, return an empty string. If more than one valid substring exists with the same minimal length, return the one that starts earliest in s1.

Key Insights

  • The problem is different from the classic "minimum window substring" because the characters of s2 must appear in order.
  • A two-pointer approach can be used to first "fast-forward" to find a valid window end where the last character of s2 is matched.
  • Once the end is found, a reverse scan is applied to find the beginning of the window by matching s2 in reverse order.
  • Updating the result when a smaller window is found is crucial.
  • The approach runs in O(n * m) time, with n and m being the lengths of s1 and s2 respectively.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s1 and m is the length of s2. Space Complexity: O(1) additional space is used apart from the input strings.

Solution

The solution uses a two-phase approach for each candidate window:

  1. Use a forward pointer to traverse s1 until we find a valid window ending at an index where the last character of s2 is matched.
  2. Once a valid end is detected, use a backward pointer starting at that index and move in reverse to find the start index of the window where s2 fully matches as a subsequence.

The algorithm repeatedly checks every possible window end where the match is complete and updates the minimal window to return the left-most minimal substring if multiple windows of the same length exist.

Code Solutions

# Python solution for Minimum Window Subsequence

def minWindow(s1: str, s2: str) -> str:
    s1_len, s2_len = len(s1), len(s2)
    min_len = float('inf')
    start_index = -1

    # Iterate through s1
    for i in range(s1_len):
        # When the current character matches the first character of s2, try to find a valid window
        if s1[i] == s2[0]:
            j = i
            k = 0
            # Move forward as long as characters match s2
            while j < s1_len and k < s2_len:
                if s1[j] == s2[k]:
                    k += 1
                j += 1
            # If entire s2 is matched, perform a backward scan
            if k == s2_len:
                end = j - 1  # end index of the valid window
                k -= 1
                # Move backward to find the start of the window
                while k >= 0:
                    if s1[j-1] == s2[k]:
                        k -= 1
                    j -= 1
                j += 1  # adjust j to the actual start index
                # Update result if the current window is smaller
                if end - j + 1 < min_len:
                    min_len = end - j + 1
                    start_index = j
    return "" if start_index == -1 else s1[start_index:start_index+min_len]

# Example usage:
# result = minWindow("abcdebdde", "bde")
# print(result)  # Expected "bcde"
← Back to All Questions