Minimum Window Subsequence

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

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

Minimum Window Subsequence

Problem Statement

A substring is a sequence of characters that sit next to each other in a string, in order, with no gaps.

A subsequence is a sequence made from another sequence by removing zero or more characters, without changing the order of what's left.

Let's look at an example with two strings:

• str1 = "abbcbabbcb"
• str2 = "acac"

Here, "abbcabbc" is a substring of str1. If we remove both "bb" sections from it, we get str2. So str2 is a subsequence of this substring. Since this is the shortest substring of str1 where str2 appears as a subsequence, the answer is "abbcabbc".

If no substring of str1 contains str2 as a subsequence, return an empty string.

If more than one substring has the same minimum length, return the one that starts earliest (has the left-most starting index).

Constraints

• 1 ≤ str1.length ≤ 2 × 10³
• 1 ≤ str2.length ≤ 100
• str1 and str2 only contain uppercase and lowercase English letters.

Examples

Sample Example 1

Input:

• str1 = "abcdebdde"
• str2 = "bde"

Output String: "bcde"

Explanation: Both "bcde" and "bdde" are substrings with the shortest possible length. But "bcde" appears earlier in str1, so it is the answer. The substring "deb" is also short, but its letters do not appear in the same order as str2, so it does not count.

Sample Example 2

Input:

• str1 = "abcdebdde"
• str2 = "bdf"

Output String: ""

Explanation: str1 does not contain the letter "f" at all. So we return an empty string.

Solution

The approach uses two passes: one going forward, and one going backward.

Step 1: Move Forward

• We go through str1 using a pointer, indexS1. We also keep a pointer for str2, called indexS2.
• Whenever the characters at both pointers match, we move indexS2 forward.
• Once indexS2 reaches the end of str2, it means we have found a spot in str1 where all of str2's characters appear, in the correct order (though maybe with extra characters mixed in, and possibly longer than needed).

Step 2: Move Backward to Trim the Start

Here's a tricky part: the substring we found by moving forward might be longer than necessary at the start.

For example, if str1 is "sssabc" and str2 is "sabc", our forward search would give us the range from index 0 to 5. But the real shortest answer should start at index 2, not 0.

To fix this, once we find a match, we move backward from the current end point:

• We go backward through str1, and backward through str2 at the same time.
• We keep moving until we've matched all characters of str2 again, this time starting from the most recent occurrence.
• This gives us the true starting point of the shortest valid substring.

Step 3: Update the Answer and Keep Searching

• Once we know the real start and end of this substring, we check if it's shorter than the best one we've found so far. If so, we save it.
• We then move indexS1 back to start and continue searching through the rest of str1, in case there's an even shorter valid substring later on.
• we set indexS1 to start and not the end because there could be a shorter string in what we have already found. Later in interation when indexS1 increment it will act as start+1 so we'll scan from next element after current start.

Code

function minWindow(str1, str2) {
  // save the size of str1 and str2
  let sizeStr1 = str1.length;
  let sizeStr2 = str2.length;

  // initialize minSubLen to a very large number (infinity)
  let minSubLen = Infinity;

  // initialize pointers to zero and the minSubsequence to an empty string
  let indexS1 = 0;
  let indexS2 = 0;
  let minSubsequence = "";

  // iterate over str1
  while (indexS1 < sizeStr1) {
    // check if the character pointed by indexS1 in str1
    // is the same as the character pointed by indexS2 in str2
    if (str1[indexS1] === str2[indexS2]) {
      // if the pointed character is the same
      // in both strings increment indexS2
      indexS2++;

      // check if indexS2 has reached the end of str2
      if (indexS2 === sizeStr2) {
        // initialize start to the index where all characters of
        // str2 were present in str1
        let start = indexS1;
        let end = indexS1;
        indexS2--;

        // decrement pointer indexS2 and start a reverse loop
        while (indexS2 >= 0) {
          // decrement pointer indexS2 until all characters of
          // str2 are found in str1
          if (str1[start] === str2[indexS2]) {
            indexS2--;
          }

          // decrement start pointer every time to find the
          // starting point of the required subsequence
          start--;
        }
        start++;

        // check if minSubLen of subsequence pointed
        // by start and end pointers is less than current minSubLen
        if (end - start + 1 < minSubLen) {
          // update minSubLen if the current subsequence is shorter
          minSubLen = end - start + 1;

          // update minimum subsequence string
          // to this new shorter string
          minSubsequence = str1.slice(start, end + 1);
        }

        // set indexS1 to start to continue checking in str1
        // after this discovered subsequence
        indexS1 = start;
        indexS2 = 0;
      }
    }

    // increment pointer indexS1 to check the next character in str1
    indexS1++;
  }

  // return the minimum window subsequence
  return minSubsequence;
}