Solution: Minimum Window Subsequence

Let's solve the Minimum Window Subsequence problem using the Sliding Window pattern.

Statement

Given two strings, str1 and str2, find the shortest substring in str1 such that str2 is a subsequence of that substring.

A substring is defined as a contiguous sequence of characters within a string. A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Let’s say you have the following two strings:

str1 = “abbcbabbcb

str2 = “acac

In this example, “abbcabbc” is a substring of str1, from which we can derive str2 simply by deleting both the instances of the character bb. Therefore, str2 is a subsequence of this substring. Since this substring is the shortest among all the substrings in which str2 is present as a subsequence, the function should return this substring, that is, “abbcabbc”.

If there is no substring in str1 that covers all characters in str2, return an empty string.

If there are multiple minimum-length substrings that meet the subsequence requirement, return the one with the left-most starting index.

Constraints:

  • 11 \leq str1.length \leq 2×1032 \times 10^3
  • 11 \leq str2.length \leq 100100
  • str1 and str2 consist of uppercase and lowercase English letters.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.