Minimum Window Subsequence — Forward Then Backward Scan

Problem Statement#

Given strings s and t, return the minimum-length substring of s that contains t as a subsequence. If multiple windows tie, return the one with the leftmost start. Return "" when no window exists.

Constraints:

• 1 <= s.length <= 2 * 10^4
• 1 <= t.length <= 100
• Both strings are lowercase English letters.

Input:  s = "abcdebdde", t = "bde"
Output: "bcde"

Input:  s = "abce", t = "ace"
Output: "abce"

Why This Problem Matters#

LeetCode 727 — Minimum Window Subsequence — is a Hard that Google and Amazon use to differentiate candidates who only know the standard sliding window from those who can adapt the window technique to ordered subsequences. Brute force is O(|s|^2 * |t|), which times out, and a DP solution costs O(|s| * |t|) time and space.

The cleanest interview answer is a forward-then-backward two-pointer pass. The technique is unusual: forward to confirm a valid right boundary, backward from that boundary to tighten the left edge. Candidates who pull this off cleanly almost always advance.

The pattern shows up in bioinformatics (shortest DNA segment containing a target gene), search engines (shortest snippet that contains the query terms in order), and log analysis (smallest event window that hits a sequence of markers).

The Core Insight#

Subsequence matching needs ordering, not contiguity. A simple forward scan that walks i through s and advances j through t finds the earliest right boundary where all of t has been matched in order. The catch is that the start index used for the forward scan may be too far left.

Once the right boundary is known, run a backward scan from that boundary matching t in reverse. The first position where the reverse scan finishes is the rightmost (tightest) valid left boundary. This compresses the window without missing any valid match.

After processing one window, restart the forward scan at left + 1 to enumerate the next candidate. Each character is visited at most |t| times, giving O(|s| * |t|) time and O(1) space. That O(1) space is what makes this preferable to DP in interviews.

Visual Dry Run#

s = "abcdebdde", t = "bde". First iteration starts at i = 0.

Window is s[1:5] = "bcde". Restart forward scan at i = 2 and verify no shorter window exists.

Solution (Optimal)#

class Solution:
    def minWindow(self, s, t):
        ans = ""
        i = 0
 
        while i < len(s):
            # Phase 1: forward scan to find a valid right boundary.
            j = 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    j += 1
                i += 1
            if j < len(t):
                break
 
            # Phase 2: backward scan to tighten the left boundary.
            k = i - 1
            j = len(t) - 1
            while j >= 0:
                if s[k] == t[j]:
                    j -= 1
                k -= 1
            k += 1
 
            # Track the leftmost shortest window.
            if not ans or i - k < len(ans):
                ans = s[k:i]
 
            # Move start past the current left boundary for the next round.
            i = k + 1
 
        return ans

var minWindow = function(s, t) {
    let ans = "";
    let i = 0;
 
    while (i < s.length) {
        let j = 0;
        while (i < s.length && j < t.length) {
            if (s[i] === t[j]) j++;
            i++;
        }
        if (j < t.length) break;
 
        let k = i - 1;
        let jb = t.length - 1;
        while (jb >= 0) {
            if (s[k] === t[jb]) jb--;
            k--;
        }
        k++;
 
        if (!ans || i - k < ans.length) {
            ans = s.slice(k, i);
        }
        i = k + 1;
    }
 
    return ans;
};

Time: O(|s| * |t|) worst case — each s index visited at most |t| times. Space: O(1) extra ignoring the output.

Common Mistakes#

• Treating the problem as substring matching, missing the gap-allowance of subsequences.
• Skipping the backward scan and using the forward start index, which often leaves the window loose.
• Off-by-one on k after the backward loop; you must increment back by one.
• Restarting the next iteration at left instead of left + 1, causing infinite loops.
• Returning early on the first valid window without comparing future windows.

Interview Tips#

• Lead with "the forward scan gives a valid right boundary; the backward scan tightens the left."
• Walk an example showing how the backward scan slides past unnecessary characters.
• Mention DP as an alternative but justify why two pointers wins on space.
• Confirm tie-breaking semantics: leftmost start when lengths are equal.

Follow-up Questions#

• How does this differ from LeetCode 76? LC 76 needs character frequencies in any order; LC 727 needs ordered subsequence matching.
• DP version? dp[i][j] is the start index of the smallest window for s[..i] matching t[..j].
• Multiple disjoint matches? The algorithm already enumerates them via i = k + 1 restarts.
• Streaming s? Maintain only the current best window and pointers; suitable for large inputs.
• Want all minimum windows? Track every window matching the minimum length seen.

Key Takeaways#

• LeetCode 727 is a Hard asked at Google and Amazon.
• Forward scan finds a valid right boundary, backward scan tightens the left.
• The two-pointer approach matches DP time but uses O(1) space.
• Restart the next iteration at left + 1 to find disjoint candidate windows.
• Off-by-one is easy: the backward loop overshoots by one, increment k back.
• Subsequence matching is ordered but allows gaps; substring matching does not.
• Tie-break ties by preferring the leftmost starting index.