Minimum Window Subsequence

Hard
777.

Minimum Window Subsequence

Minimum Window Subsequence is a hard coding problem on strings, dynamic programming and two pointers, asked in Amazon, Google and Uber interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {string}
 */
var minWindow = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Window Subsequence — Solution in Python, Java & C++

Minimum Window Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Window Subsequence is a hard coding problem on strings, dynamic programming and two pointers, asked in Amazon, Google and Uber interviews.

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.

Hints for Minimum Window Subsequence

  1. Hint 1

    A subsequence match, not a substring match — the characters of s2 need only appear in order.

  2. Hint 2

    Greedily match s2 forward from a start position; the first position where the match completes is the tightest possible end.

  3. Hint 3

    From that end, walk backwards matching s2 in reverse to pull the start as far right as it will go.

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]

Java

public static String minWindow(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int bestStart = -1, bestLen = n + 1;
    int i = 0;
    while (i < n) {
        int j = 0, k = i;
        while (k < n) {
            if (s1.charAt(k) == s2.charAt(j)) {
                j++;
                if (j == m) break;
            }
            k++;
        }
        if (j < m) break;
        int 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);
}

C++

string minWindow(string s1, string s2) {
    int n = (int) s1.size(), m = (int) s2.size();
    int bestStart = -1, bestLen = n + 1;
    int i = 0;
    while (i < n) {
        int j = 0, k = i;
        while (k < n) {
            if (s1[k] == s2[j]) {
                j++;
                if (j == m) break;
            }
            k++;
        }
        if (j < m) break;
        int back = k, jj = m - 1;
        while (jj >= 0) {
            if (s1[back] == s2[jj]) jj--;
            if (jj >= 0) back--;
        }
        if (k - back + 1 < bestLen) {
            bestLen = k - back + 1;
            bestStart = back;
        }
        i = back + 1;
    }
    return bestStart < 0 ? string("") : s1.substr(bestStart, bestLen);
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming