Minimum Window Subsequence

Minimum Window Subsequence

What is this problem about?

The Minimum Window Subsequence problem gives you two strings S and T. Find the minimum length window (substring of S) that contains T as a subsequence. Unlike "contains T as a substring," T's characters must appear in order within the window but not necessarily consecutively. This Minimum Window Subsequence coding problem requires a two-pass sliding pointer approach or dynamic programming.

Why is this asked in interviews?

Meta, eBay, LinkedIn, and Google ask this because it's a harder cousin of the classic Minimum Window Substring but with the subsequence condition instead of full character coverage. It tests whether candidates can apply the sliding window interview pattern to subsequence matching — a non-trivial adaptation. The sliding window, string, and dynamic programming interview pattern is the core.

Algorithmic pattern used

Two-pointer / greedy scan. For each starting position in S, scan forward to find the end of the smallest window containing T as a subsequence. Then scan backwards from that end to find the tightest starting position. Track the minimum window length found. Alternatively, use DP: dp[i][j] = starting index in S such that S[dp[i][j]..i] contains T[0..j-1] as subsequence. Time: O(|S| * |T|).

Example explanation

S = "abcde", T = "ace".

• Start at S[0]='a': scan forward matching T: 'a' at 0, 'c' at 2, 'e' at 4. Window [0..4] = "abcde", length 5.
• Scan backward from 4: 'e'=S[4] ✓, 'c'=S[2] ✓, 'a'=S[0] ✓. Tightest start = 0. Window = "abcde".
• Start from S[1]: 'a' not found until... no better window found. Minimum = 5 ("abcde").

S = "abcbdaace", T = "ace":

• At start 5: 'a'=5, 'c'=7 (wait, check character matching). Find window "ace" directly at length 3. Minimum = 3.

Common mistakes candidates make

• Confusing subsequence matching with substring matching.
• Not scanning backward after finding the end of a window (missing tighter starts).
• O(|S|² * |T|) brute force — must use the greedy or DP O(|S| * |T|) approach.
• Not handling the case where no valid window exists (return "").

Interview preparation tip

Minimum Window Subsequence is an excellent advanced follow-up to Minimum Window Substring. The key distinction: substring requires all characters present (use counts), subsequence requires ordered occurrence (use pointers). The backward scan after finding a window end is the unique insight here — it finds the tightest possible starting point for that end, minimizing window length. Practice both variants together to internalize the difference in approach and implementation.