01. Minimum Window Subsequence

Difficulty:HardPattern:Two Pointers Contract ScanTime:O(|s1| * |s2|)Space:O(1)

Given strings s1 and s2, return the minimum contiguous substring $W$ of s1 such that s2 is a subsequence of $W$.

How It Works & Algorithmic Design

Solves using Two-Pointer Forward Match and Backward Contract Expansion:

Forward Match: Advance i1 over s1 matching characters in s2 via i2++.
Backward Contract: When i2 === s2.length (full subsequence matched):
- Set end = i1.
- Decrement i1 backward while contracting s2 index i2-- to find exact starting index start.
Update Min Window: Check window length end - start + 1 against best answer.
Resume: Reset i2 = 0 and resume i1 = start + 1.

Why This Approach Works Best

Combines forward scanning with backward contraction to evaluate optimal windows in $O(|s1| \times |s2|)$ time and $O(1)$ space.

Example Walkthrough

Input: s1 = "abcdebdde", s2 = "bde"

Target subsequence.

Matching Windows: "bcde" (len 4) and "bcdebdde" -> contracted to "bcde" and "bcde" / "bdde" (len 4).

Subsequence substrings.

Output: "bcde"

Shortest substring.

Answer: Minimum Window Subsequence implementation

function minWindow(s1, s2) {
  let i1 = 0, i2 = 0;
  let minLen = Infinity, startIdx = -1;
  while (i1 < s1.length) {
    if (s1[i1] === s2[i2]) {
      i2++;
      if (i2 === s2.length) {
        let end = i1;
        i2--;
        while (i2 >= 0) {
          if (s1[i1] === s2[i2]) i2--;
          i1--;
        }
        i1++;
        if (end - i1 + 1 < minLen) {
          minLen = end - i1 + 1;
          startIdx = i1;
        }
        i2 = 0;
      }
    }
    i1++;
  }
  return startIdx === -1 ? '' : s1.substring(startIdx, startIdx + minLen);
}

💡 Match sequence characters forward and shrink window backward to locate minimal length sub-strings.

Key Takeaways

Forward scan finds complete subsequence matches.
Backward contraction pinpoints the minimal left boundary.
Runs in $O(|s1| \times |s2|)$ time and $O(1)$ extra space.