Minimum Window Subsequence

50 min · minWindow()

A long activity log contains the events you need in the right order, but they're spread apart. How little of the log can you keep without losing that ordered trail?

You're given two lowercase strings, s1 and s2.

A contiguous substring is one unbroken slice of a string. A subsequence keeps characters in their original order but may skip characters between them.

Return the shortest contiguous substring W of s1 in which s2 appears as a subsequence. If no such window exists, return "".

A few ground rules:

You may skip characters inside W while matching s2, but you can't reorder them.
If several shortest windows have the same length, return the one with the leftmost starting index in s1.
The returned window must contain consecutive characters from s1.

Constraints

1 <= s1.length <= 2_000
1 <= s2.length <= 100
s1 and s2 contain only lowercase English letters.

Hints

Anchor a starting point

Fix a start in s1, then walk right while matching the next needed character from s2. The first end that completes s2 is the best end for that fixed start.

Store the latest beginning

A prefix is a slice that starts at index 0. For each prefix of s2, track the latest index in s1 where a matching subsequence could have started. A later start gives a shorter window for the same end.

Update prefixes backward

When s1[i] matches s2[j], extend the answer for prefix j - 1. Visit j from right to left so the same character from s1 can't satisfy two positions in s2.

Follow-up

Could you return the exact indices in s1 that matched each character of s2, not just the surrounding window? What extra information would your states need to remember?

Visible cases

Examples

Example 1

ready

Input: s1 = "abcdebdde" s2 = "bde"
Expected: "bcde"
Why: both 'bcde' and 'bdde' work at length 4, so the leftmost one wins

Example 2

ready

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl" s2 = "u"
Expected: ""
Why: the required character never appears, so no window exists

Example 3

ready

Input: s1 = "abcab" s2 = "ac"
Expected: "abc"
Why: a and c appear in order inside the shortest slice 'abc'

Interview signal

Asked at

AmazonGoogle

Try every start

Fix each possible start in s1. From there, scan right and match each needed character of s2 at its first opportunity. Stop at the first end that completes the subsequence: any later end would only make this fixed-start window longer.

Keep a candidate only when it's strictly shorter than the best one. Because starts are visited from left to right, ignoring equal lengths preserves the leftmost answer.

def min_window(s1: str, s2: str) -> str:
    best_start = -1
    best_length = len(s1) + 1
 
    for start in range(len(s1)):
        target = 0
        for end in range(start, len(s1)):
            if s1[end] == s2[target]:
                target += 1
            if target == len(s2):
                length = end - start + 1
                if length < best_length:
                    best_start = start
                    best_length = length
                break
 
    if best_start == -1:
        return ""
    return s1[best_start:best_start + best_length]

An absent target can make almost every start scan to the end of s1.

Time O(|s1|²). Space O(1) beyond the returned slice.

Latest-start subsequence DP

Dynamic programming (DP) saves the best result for smaller subproblems and extends those results into larger ones. Here, starts[j] stores the latest starting index of a subsequence matching s2[0:j + 1] within the part of s1 seen so far.

Why keep the latest start? For a fixed ending index, a later start always produces a shorter window.

Scan s1 from left to right. For each character, update matching positions of s2 from right to left. That backward order matters: it prevents one character in s1 from advancing two positions of s2 during the same iteration.

def min_window(s1: str, s2: str) -> str:
    starts = [-1] * len(s2)
    best_start = -1
    best_length = len(s1) + 1
 
    for end, char in enumerate(s1):
        completed_start = -1
 
        for target in range(len(s2) - 1, -1, -1):
            if char != s2[target]:
                continue
 
            if target == 0:
                starts[0] = end
                if len(s2) == 1:
                    completed_start = end
            elif starts[target - 1] != -1:
                starts[target] = starts[target - 1]
                if target == len(s2) - 1:
                    completed_start = starts[target]
 
        if completed_start != -1:
            length = end - completed_start + 1
            if length < best_length:
                best_start = completed_start
                best_length = length
 
    if best_start == -1:
        return ""
    return s1[best_start:best_start + best_length]

Whenever the last position of s2 is reached, completed_start is the latest possible start for that end, so the candidate is the shortest window ending there. Checking every end covers the global optimum. Updating only for a strictly shorter candidate keeps the first — and therefore leftmost — window on a tie.

Time O(|s1| · |s2|). Space O(|s2|) for the DP states.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrays1: string · s2: string

Expected

"bcde"

Run: visible + custom · Submit: full suite