Minimum Window Subsequence - Solution & Explanation

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.