727. Minimum Window Subsequence Solution

The problem

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part.

If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of s2 in the window must occur in order.

Example 2:

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""

Constraints:

1 <= s1.length <= 2 * 10⁴
1 <= s2.length <= 100
s1 and s2 consist of lowercase English letters.

Approach overview

Problem Overview: Given two strings S and T, find the smallest substring of S such that T appears inside it as a subsequence. Characters in T must appear in order but do not need to be contiguous. If multiple windows exist, return the one with the minimum length.

Approach 1: Brute Force Subsequence Check (O(n^2 * m) time, O(1) space)

Start a window at every index i in S. From that position, scan forward trying to match characters of T sequentially. If the full subsequence is found ending at position j, record the window S[i...j]. Repeat for all starting indices and keep the smallest valid window. This approach works because subsequence matching is straightforward: iterate through S while advancing a pointer in T when characters match. However, repeatedly rescanning the string makes the algorithm expensive for large inputs.

This method highlights the core requirement of subsequence matching, but its nested scanning leads to poor performance. It is mainly useful for understanding the problem constraints before optimizing with dynamic programming.

Approach 2: Dynamic Programming Window Tracking (O(n * m) time, O(n * m) space)

The optimized approach builds a DP table where dp[i][j] stores the starting index in S of a subsequence matching the first j characters of T and ending at position i. Iterate through S and update transitions based on whether S[i] matches T[j]. If characters match, inherit the start index from dp[i-1][j-1]; otherwise carry forward dp[i-1][j]. Whenever a full subsequence match for T is detected, compute the window length and update the best result.

The key insight: instead of restarting subsequence searches repeatedly, the DP table remembers where each partial match began. That converts repeated scans into constant-time lookups. The algorithm processes each pair of indices once, giving predictable O(n * m) time.

This technique relies heavily on string processing and sequence alignment patterns often seen in sliding window-style substring problems, though the window boundaries here are derived from DP states rather than two pointers.

Recommended for interviews: Interviewers typically expect the dynamic programming solution. Starting with the brute force explanation demonstrates that you understand subsequence matching, but the DP approach shows the ability to eliminate repeated scans and track partial matches efficiently. Discussing the transition rule and how the start index propagates through the table signals strong problem‑solving depth for hard string problems.

Solution

We define f[i][j] to represent the starting position of the shortest substring of the first i characters of string s1 that contains the first j characters of string s2. If it does not exist, it is 0.

We can derive the state transition equation:

$f[i][j] = \begin{cases} i, & j = 1 and s1[i-1] = s2[j] \ f[i - 1][j - 1], & j > 1 and s1[i-1] = s2[j-1] \ f[i - 1][j], & s1[i-1] \ne s2[j-1] \end{cases}

Next, we only need to traverse s1. If f[i][n] \gt 0, update the starting position and length of the shortest substring. Finally, return the shortest substring.

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of strings s1 and s2$, respectively.

Python

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i, a in enumerate(s1, 1):
            for j, b in enumerate(s2, 1):
                if a == b:
                    f[i][j] = i if j == 1 else f[i - 1][j - 1]
                else:
                    f[i][j] = f[i - 1][j]
        p, k = 0, m + 1
        for i, a in enumerate(s1, 1):
            if a == s2[n - 1] and f[i][n]:
                j = f[i][n] - 1
                if i - j < k:
                    k = i - j
                    p = j
        return "" if k > m else s1[p : p + k]

Java

class Solution {
    public String minWindow(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    f[i][j] = j == 1 ? i : f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        int p = 0, k = m + 1;
        for (int i = 1; i <= m; ++i) {
            if (s1.charAt(i - 1) == s2.charAt(n - 1) && f[i][n] > 0) {
                int j = f[i][n] - 1;
                if (i - j < k) {
                    k = i - j;
                    p = j;
                }
            }
        }
        return k > m ? "" : s1.substring(p, p + k);
    }
}

C++

class Solution {
public:
    string minWindow(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = j == 1 ? i : f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        int p = 0, k = m + 1;
        for (int i = 1; i <= m; ++i) {
            if (s1[i - 1] == s2[n - 1] && f[i][n]) {
                int j = f[i][n] - 1;
                if (i - j < k) {
                    k = i - j;
                    p = j;
                }
            }
        }
        return k > m ? "" : s1.substr(p, k);
    }
};

TypeScript

function minWindow(s1: string, s2: string): string {
    const m = s1.length;
    const n = s2.length;
    const f: number[][] = Array(m + 1)
        .fill(0)
        .map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (s1[i - 1] === s2[j - 1]) {
                f[i][j] = j === 1 ? i : f[i - 1][j - 1];
            } else {
                f[i][j] = f[i - 1][j];
            }
        }
    }
    let p = 0;
    let k = m + 1;
    for (let i = 1; i <= m; ++i) {
        if (s1[i - 1] === s2[n - 1] && f[i][n]) {
            const j = f[i][n] - 1;
            if (i - j < k) {
                k = i - j;
                p = j;
            }
        }
    }
    return k > m ? '' : s1.slice(p, p + k);
}

func minWindow(s1 string, s2 string) string {
	m, n := len(s1), len(s2)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s1[i-1] == s2[j-1] {
				if j == 1 {
					f[i][j] = i
				} else {
					f[i][j] = f[i-1][j-1]
				}
			} else {
				f[i][j] = f[i-1][j]
			}
		}
	}
	p, k := 0, m+1
	for i := 1; i <= m; i++ {
		if s1[i-1] == s2[n-1] && f[i][n] > 0 {
			j := f[i][n] - 1
			if i-j < k {
				k = i - j
				p = j
			}
		}
	}
	if k > m {
		return ""
	}
	return s1[p : p+k]
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Subsequence Scan	O(n^2 * m)	O(1)	Conceptual baseline or when input size is very small
Dynamic Programming Window Tracking	O(n * m)	O(n * m)	General optimal solution for large strings and interview settings

Frequently asked questions

Is Minimum Window Subsequence easy or hard?

Minimum Window Subsequence is classified as a hard problem on LeetCode. The challenge comes from combining subsequence matching with window minimization and avoiding repeated scans of the string. Dynamic programming is typically required to reach optimal complexity.

Minimum Window Subsequence Python/Java solution

Most implementations follow the same dynamic programming structure regardless of language. Create a 2D DP array, iterate through S and T to update subsequence start indices, and track the minimum window whenever a full match of T is completed. The logic translates directly to Python, Java, C++, Go, and TypeScript.

How to solve Minimum Window Subsequence in O(n * m)?

Use dynamic programming to track where each partial subsequence begins. Maintain dp[i][j] representing the starting index in S where the first j characters of T form a subsequence ending at i. When the final column (matching all of T) is reached, compute the window length and update the best answer.

What is the best approach for Minimum Window Subsequence?

The most reliable approach uses dynamic programming. Build a DP table that tracks the starting index of subsequences matching prefixes of T while scanning S. This avoids repeatedly rescanning the string and finds the smallest valid window in O(n * m) time and O(n * m) space.

Is Minimum Window Subsequence asked at Google/Amazon/Meta?

Minimum Window Subsequence appears in interview preparation lists for companies like Google, Amazon, and Meta because it combines subsequence matching with dynamic programming and window reasoning. It is considered a strong test of advanced string manipulation skills.

What data structure is used in Minimum Window Subsequence?

The primary structure is a dynamic programming table that tracks subsequence start indices. The algorithm also relies on sequential string traversal and index tracking rather than complex data structures like heaps or trees.

What is the time complexity of Minimum Window Subsequence?

The optimal dynamic programming solution runs in O(n * m) time, where n is the length of S and m is the length of T. Each pair of indices is processed once while updating subsequence start positions. Space complexity is also O(n * m) for the DP table.

Minimum Window Subsequence solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Minimum Window Subsequence solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems