Min Window Subsequence LeetCode 727

LeetCode 727 Minimum Window Subsequence gives you two strings S1 and S2, and asks you to find the minimum-length contiguous substring of S1 such that S2 is a subsequence of that substring. A subsequence means the characters of S2 appear in the substring in order, but not necessarily contiguously. If no such window exists, return an empty string.

This problem is distinct from Minimum Window Substring (LeetCode 76), which only requires each character of T to appear in the window with the right frequency. Here, the order matters strictly: the characters of S2 must appear in order within the chosen window. This ordering constraint makes a pure sliding window insufficient and requires either a forward-backward two-pointer strategy or a DP approach.

Understanding the problem precisely helps avoid common mistakes. The window is a contiguous substring of S1, but S2 is matched as a subsequence within that window. If S2 = "abc" and S1 = "axbycz", the window "axbycz" works because a, b, c appear in order. But "axbyc" also works and is shorter. The goal is to find the globally shortest such window across all starting positions in S1.

The brute force approach tries every possible starting position in S1. For each index i in S1, use a greedy forward scan: walk through S1 from position i, trying to match all characters of S2 in order. When all characters of S2 are matched, record the window S1[i..j] and update the global minimum if this window is shorter than the current best.

This approach runs in O(m * n) time in the worst case, where m = len(S1) and n = len(S2), because for each of the m starting positions in S1 we may scan up to m characters trying to match n characters of S2. The space complexity is O(1) beyond storing the result. While correct, it may be too slow for the given constraints of S1 up to 20,000 characters.

The brute force correctly handles all cases: multiple valid windows, windows starting at the first or last character of S1, and the empty-string return when no window exists. It establishes the baseline logic that more efficient approaches optimize. Recognizing that the brute force does redundant work — restarting from each i independently — motivates the forward-backward trick that avoids that redundancy.

The forward-backward two-pointer approach works in two passes per candidate window. In the forward pass, use a pointer j into S2 starting at 0. Walk through S1 with pointer i; each time S1[i] == S2[j], advance j. When j reaches len(S2), all characters of S2 have been matched in order — record i as the end of a candidate window.

In the backward pass, start at the recorded end position and walk backward through S1. Use a pointer k into S2 starting at len(S2) - 1. Each time S1[i] == S2[k], decrement k. When k reaches -1, all characters of S2 have been matched in reverse — the current i is the earliest valid start for a window ending at the recorded end. The window is S1[i..end].

After recording this candidate window, continue the outer loop from end + 1 to search for the next candidate window. Track the global minimum window across all candidates. This approach runs in O(m * n) worst-case time but is typically much faster in practice because the backward pass quickly identifies the true minimum start without redundant forward rescanning.

The DP approach uses a 2D table dp[i][j] where dp[i][j] represents the starting index in S1 at which the first j characters of S2 are matched as a subsequence ending at position i in S1. The transition is: if S1[i] == S2[j], then dp[i][j] = dp[i-1][j-1] (propagate the start from where the previous character was matched); otherwise dp[i][j] = dp[i-1][j] (carry forward the best start seen so far without advancing j).

Initialize dp[i][0] = i for all i, meaning zero characters of S2 matched starting at position i. When dp[i][n] (where n = len(S2)) is not infinity, a complete match of S2 ends at position i in S1 starting from dp[i][n]. The window is S1[dp[i][n]..i+1]. Scan all i to find the minimum-length such window.

Space can be optimized to O(n) by only keeping one row of the DP table at a time, since each row only depends on the previous row. The DP formulation is more systematic and handles edge cases cleanly, but the two-pointer approach is typically preferred in interviews for its lower constant factors and O(1) space.

A critical optimization in the forward-backward approach is where to resume the outer loop after finding each candidate window. A naive implementation might restart from start + 1 after each match — similar to a brute force fallback. The correct optimization is to resume from end + 1, the position immediately after the end of the just-found window.

Restarting from end + 1 is valid because any window starting before end + 1 and ending after end has already been covered: the backward pass found the shortest window ending at end starting from the earliest valid position. There is no shorter window ending at or before end that we have missed. Moving to end + 1 ensures we scan all of S1 without redundant overlap.

This optimization does not change the worst-case O(m * n) complexity — in the worst case, every character of S1 matches the first character of S2 and triggers a full backward scan. But for typical inputs, it significantly reduces the number of iterations by skipping over already-processed regions of S1 rather than re-examining them from each possible starting position.

Python two-pointer: def minWindow(s1, s2): result = ""; n1, n2 = len(s1), len(s2); i = 0. While i < n1: j = 0; while i < n1 and j < n2: if s1[i] == s2[j]: j += 1; i += 1. If j == n2: end = i - 1; k = n2 - 1; while k >= 0: if s1[i-1] == s2[k]: k -= 1; i -= 1. start = i; window = s1[start:end+1]; if not result or len(window) < len(result): result = window; i = end + 1. Return result. O(m*n) worst case, O(1) space.

Java two-pointer: public String minWindow(String s1, String s2) { String result = ""; int n1 = s1.length(), n2 = s2.length(), i = 0; while (i < n1) { int j = 0; while (i < n1 && j < n2) { if (s1.charAt(i) == s2.charAt(j)) j++; i++; } if (j == n2) { int end = i - 1; int k = n2 - 1; while (k >= 0) { if (s1.charAt(i-1) == s2.charAt(k)) k--; i--; } int start = i; String window = s1.substring(start, end + 1); if (result.isEmpty() || window.length() < result.length()) result = window; i = end + 1; } } return result; }

Both implementations follow the same structure: an outer loop driving forward scans, an inner forward scan matching S2 left-to-right, a backward scan matching S2 right-to-left to find the minimum start, and advancement to end + 1 for the next iteration. The key correctness point is that the backward pass decrements both the S1 pointer and the S2 reverse pointer simultaneously, stopping when all of S2 has been matched in reverse.

Minimum Window Substring (LeetCode 76) is the closest cousin: find the minimum window in S containing all characters of T with the right frequencies. The key difference is that LeetCode 76 does not require order — a hash map of character counts suffices. LeetCode 727 adds the ordering constraint, requiring the subsequence matching logic. Understanding both problems clarifies when a frequency map is sufficient versus when a sequential match is required.

Is Subsequence (LeetCode 392) is the foundational building block: given s and t, determine if s is a subsequence of t using a single forward two-pointer scan. LeetCode 727 generalizes this to finding the minimum window over which the subsequence check succeeds. Longest Common Subsequence (LeetCode 1143) uses a similar DP table but maximizes length rather than minimizing window size. These three problems form a natural progression in subsequence reasoning.

The window-subsequence family also includes problems like Distinct Subsequences (LeetCode 115) and Shortest Supersequence. The common thread is reasoning about characters appearing in order within strings, which requires either explicit pointer tracking or DP state that carries positional information. Mastering the forward-backward two-pointer technique for LeetCode 727 provides a reusable mental model for any problem that combines window-finding with subsequence constraints.