Grokking the Coding Interview Patterns/

...

/

Solution: Minimum Window Subsequence

Solution: Minimum Window Subsequence

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

We'll cover the following...

Statement

Given two strings, s1 and s2, find and return the shortest substring of s1 in which all the characters of s2 appear in the same order, but not necessarily next to each other (i.e., s2 should be a subsequence of the substring).

If no such substring exists, return an empty string "". If there are multiple shortest substrings, return the one that appears first in s1 (i.e., with the left-most starting index).

Note: A substring is a contiguous sequence of characters within a string. A subsequence is a sequence of characters that can be derived from a string by deleting some characters without changing the order of the remaining characters. For example, “edu” is a substring and “cave” is a subsequence of “educative.”

Constraints:

  • 1≤1 \leq s1.length ≤2×103\leq 2 \times 10^{3}

  • 1≤1 \leq s2.length ≤100\leq 100

  • s1 and s2 consist of uppercase and lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach would be to generate all possible substrings of str1 and then check which substrings contain str2 as a subsequence. Out of all the substrings in str1 that contain str2 as a ...