Get started

Minimum Window Subsequence — Hard Problem & Solution

Find the shortest contiguous substring of s1 that contains s2 as a subsequence. If there is none, return the empty string.

Problem statement

Find the shortest contiguous substring of s1 that contains s2 as a subsequence.

If there is none, return the empty string. If several are equally short, return the one that starts earliest.

Example 1

Input: s1 = "codekairo", s2 = "dei"
Output: "dekai"
Explanation: The only `d` is at index 2, and the window must reach the `i` at index 6.

Example 2

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: "bdde" is also a window but it is longer.

Example 3

Input: s1 = "codekairo", s2 = "zz"
Output: ""
Explanation: No window contains it.

Constraints

  • 1 <= s1.length <= 20000
  • 1 <= s2.length <= 100
  • Both strings consist of lowercase English letters.

How to solve Minimum Window Subsequence

Two greedy passes per candidate. Going forward finds the earliest end that can complete the match; going backward from that end finds the latest start that still works. Together they produce the minimal window beginning at or after the current position.

Approach

  1. From i, scan forward matching characters of s2 in order; stop when the last one is consumed, at index k.
  2. If the scan runs off the end, no further window exists — stop.
  3. From k, scan backward matching s2 in reverse; the position where the first character is consumed is the tightest start back.
  4. Record the window and restart the outer scan at back + 1.

Why it works

The forward scan is greedy-earliest, so no window starting at or after i can end before k. The backward scan is greedy-latest from that fixed end, so no window ending at k can start after back. Restarting at back + 1 skips only starts whose optimal window is the one just recorded, so nothing shorter is missed, and each character is visited a bounded number of times.

Complexity

  • Time — O(n · m) in the worst case
  • Space — O(1) beyond the output

Pitfalls

  • Treating the requirement as a substring match misses every window with characters interleaved.
  • Restarting the outer scan at i + 1 instead of back + 1 is correct but slower, and restarting at k + 1 skips valid windows.
  • Ties are broken by the earliest start, so record only on a strictly shorter window.

Reference solution

Python

def minWindow(s1: str, s2: str) -> str:
    n, m = len(s1), len(s2)
    best_start, best_len = -1, n + 1
    i = 0
    while i < n:
        j, k = 0, i
        while k < n:
            if s1[k] == s2[j]:
                j += 1
                if j == m:
                    break
            k += 1
        if j < m:
            break
        back, jj = k, m - 1
        while jj >= 0:
            if s1[back] == s2[jj]:
                jj -= 1
            if jj >= 0:
                back -= 1
        if k - back + 1 < best_len:
            best_len = k - back + 1
            best_start = back
        i = back + 1
    return "" if best_start < 0 else s1[best_start:best_start + best_len]

JavaScript

var minWindow = function(s1, s2) {
    var n = s1.length, m = s2.length;
    var bestStart = -1, bestLen = n + 1;
    var i = 0;
    while (i < n) {
        var j = 0, k = i;
        while (k < n) {
            if (s1.charAt(k) === s2.charAt(j)) {
                j++;
                if (j === m) break;
            }
            k++;
        }
        if (j < m) break;
        var back = k, jj = m - 1;
        while (jj >= 0) {
            if (s1.charAt(back) === s2.charAt(jj)) jj--;
            if (jj >= 0) back--;
        }
        if (k - back + 1 < bestLen) { bestLen = k - back + 1; bestStart = back; }
        i = back + 1;
    }
    return bestStart < 0 ? "" : s1.substring(bestStart, bestStart + bestLen);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue