Log inSign up
hardleetcodeNot Started

Minimum Window Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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

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 · Example:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: "bcde" is the substring and "bde" is a subsequence of "bcde". "bdde" is also a candidate, but "bcde" occurs earlier.

Example 2 · Example:

Input: s1 = "jmeqqaewfrgt", s2 = "u"
Output: ""
Explanation: Character "u" is not present in s1.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate substring containment vs subsequence containment.
  • Implement bidirectional two-pointer window contraction.
  • Achieve O(1) auxiliary memory window tracking.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding shortest contiguous substring that contains a target pattern as an ordered subsequence.
  • Optimizing window boundaries with bidirectional scanning.

Algorithmic Decision Tree:

  • Forward-Backward Two Pointers
  • Subsequence Window Contraction

Connected Patterns:

Minimum Window SubstringLongest Common SubsequenceIs Subsequence

1. 2D Dynamic Programming (DP Table)

Intuition

Define dp[i][j] as the starting index in s1 (1-indexed) of the shortest substring ending at s1[i-1] that contains s2[0...j-1] as a subsequence. If s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1]. Else dp[i][j] = dp[i-1][j]. Find the minimum window length across all dp[i][T].

When to apply: Standard DP table formulation.

Algorithm

  1. Initialize dp[S + 1][T + 1] with 0.
  2. For i from 1 to S: dp[i][0] = i.
  3. For i from 1 to S:
  4. For j from 1 to T:
  5. If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1].
  6. Else: dp[i][j] = dp[i-1][j].
  7. Find minimum i - dp[i][T] + 1 among valid dp[i][T] > 0.
  8. Return minimum substring or empty string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string minWindow(std::string s1, std::string s2) {
8 int m = s1.size(), n = s2.size();
9 std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
10
11 for (int i = 0; i <= m; ++i) dp[i][0] = i + 1;
12
13 for (int i = 1; i <= m; ++i) {
14 for (int j = 1; j <= n; ++j) {
15 if (s1[i - 1] == s2[j - 1]) {
16 dp[i][j] = dp[i - 1][j - 1];
17 } else {
18 dp[i][j] = dp[i - 1][j];
19 }
20 }
21 }
22
23 int start = 0, minLen = m + 1;
24 for (int i = 1; i <= m; ++i) {
25 if (dp[i][n] > 0) {
26 int len = i - dp[i][n] + 1;
27 if (len < minLen) {
28 minLen = len;
29 start = dp[i][n] - 1;
30 }
31 }
32 }
33
34 return minLen == m + 1 ? "" : s1.substr(start, minLen);
35 }
36};
37
38int main() {
39 Solution sol;
40 std::cout << sol.minWindow("abcdebdde", "bde") << std::endl; // bcde
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(S * T) — Fills an S x T dynamic programming table.
  • Space complexity: O(S * T)

Why Brute Force Doesn't Scale:

Bidirectional two-pointer scanning achieves O(1) auxiliary memory.

Zero table allocations.

2. Space-Optimized 1D Dynamic Programming

Intuition

Observe that dp[i][j] only depends on previous row dp[i-1]. We compress the DP table into a single 1D array or two rows of size S + 1.

When to apply: When memory efficiency is required for DP.

Algorithm

  1. Initialize dp array of size m + 1 with 1-based indices.
  2. For each character in s2:
  3. Update new_dp array matching characters in s1.
  4. Find minimum difference i - dp[i] across all valid matching ends.
  5. Return optimal substring.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string minWindow(std::string s1, std::string s2) {
8 int m = s1.size(), n = s2.size();
9 std::vector<int> dp(m + 1, 0);
10 for (int i = 0; i <= m; ++i) dp[i] = i + 1;
11
12 for (int j = 1; j <= n; ++j) {
13 std::vector<int> next_dp(m + 1, 0);
14 for (int i = 1; i <= m; ++i) {
15 if (s1[i - 1] == s2[j - 1]) {
16 next_dp[i] = dp[i - 1];
17 } else {
18 next_dp[i] = next_dp[i - 1];
19 }
20 }
21 dp = std::move(next_dp);
22 }
23
24 int start = 0, minLen = m + 1;
25 for (int i = 1; i <= m; ++i) {
26 if (dp[i] > 0) {
27 int len = i - dp[i] + 1;
28 if (len < minLen) {
29 minLen = len;
30 start = dp[i] - 1;
31 }
32 }
33 }
34 return minLen == m + 1 ? "" : s1.substr(start, minLen);
35 }
36};
37
38int main() {
39 Solution sol;
40 std::cout << sol.minWindow("abcdebdde", "bde") << std::endl; // bcde
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(S * T) — 1D array of size S updated T times.
  • Space complexity: O(S)

3. Forward Scan & Backward Contraction (Optimal O(1) Space)

Intuition

Initialize i = 0, j = 0. While i < s1.length: 1. Advance i matching s1[i] == s2[j] -> j++. 2. When j == s2.length, we found a valid end at end = i - 1. Reverse scan backwards: j = s2.length - 1, decrement end whenever s1[end] == s2[j] -> j--. When j < 0, start = end + 1 is the optimal start index. 3. Update shortest window if (i - start) < minLen. 4. Reset i = start + 1, j = 0 to continue searching.

When to apply: The standard gold standard solution.

Algorithm

  1. Initialize i = 0, j = 0, minLen = infinity, minStart = -1.
  2. While i < s1.length:
  3. If s1[i] == s2[j]: j++.
  4. If j == s2.length (valid window end found):
  5. end = i.
  6. j = s2.length - 1.
  7. While j >= 0:
  8. If s1[end] == s2[j]: j--.
  9. end--.
  10. start = end + 1.
  11. If i - start + 1 < minLen:
  12. minLen = i - start + 1; minStart = start.
  13. i = start; j = 0.
  14. i++.
  15. Return minStart == -1 ? "" : s1.substr(minStart, minLen).

Bidirectional Forward Match and Backward Shrink Convergence

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d, e, b, d, d, e]
Current operationSTEP 1 OF 6
Observation: Scan forward in s1 to find characters of s2 = "bde" in sequence: 'b' at idx 1, 'd' at idx 3, 'e' at idx 4
Visual state
Values and pointers at this exact step
array
S
a
b
c
d
e
b
0
1
↑ Matched 'b'
2
3
↑ Matched 'd'
4
↑ Matched 'e' (Forward complete)
5
Variables at this step
forwardMatch
true
s1Idx
4
s2MatchedAll
true
candidateSubstr
bcde
length
4
Why this step matters

Observation: Scan forward in s1 to find characters of s2 = "bde" in sequence: 'b' at idx 1, 'd' at idx 3, 'e' at idx 4.

Decision: All characters of s2 matched. Now reverse scan from index 4 backward to minimize window start.

Invariant: Forward scan locates an upper bound end index.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string minWindow(std::string s1, std::string s2) {
7 int m = s1.size(), n = s2.size();
8 int minLen = m + 1, minStart = -1;
9 int i = 0, j = 0;
10
11 while (i < m) {
12 if (s1[i] == s2[j]) {
13 j++;
14 if (j == n) {
15 // Backward contraction
16 int end = i;
17 j = n - 1;
18 while (j >= 0) {
19 if (s1[end] == s2[j]) {
20 j--;
21 }
22 end--;
23 }
24 int start = end + 1;
25 if (i - start + 1 < minLen) {
26 minLen = i - start + 1;
27 minStart = start;
28 }
29 i = start;
30 j = 0;
31 }
32 }
33 i++;
34 }
35 return minStart == -1 ? "" : s1.substr(minStart, minLen);
36 }
37};
38
39int main() {
40 Solution sol;
41 std::cout << sol.minWindow("abcdebdde", "bde") << std::endl; // bcde
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(S * T) — Forward scan visits each index; backward scan steps back at most s2.length characters.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Dynamic Programming DP[i][j]O(S * T)O(S * T) or O(S)Classic DP formulation recording earliest start index for each prefix.Requires DP table allocation.
2.Forward Scan & Backward Contraction Two Pointers (Optimal)OptimalO(S * T)O(1) extra spaceStrictly O(1) auxiliary space, highly intuitive bidirectional sliding window.Backtracks s1 pointer to start + 1.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not performing the backward contraction phase, which causes the start index to include redundant prefix characters from earlier in s1.

Pitfall 2:

Forgetting to reset i = start after finding a window, skipping potential overlapping optimal windows.

Crucial Edge Cases to Validate:

  • s2 is not a subsequence of s1: minStart remains -1, returns empty string "".
  • Multiple windows of identical minimum length: Strictly preserves the earliest/leftmost starting window.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly contrast this problem with 'Minimum Window Substring' (which uses character counts without order) vs this problem (which strictly enforces subsequence ordering).
  2. Explain the forward-find, backward-contract pattern.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the backward scan step crucial after forward matching completes?

Back to DSA Sheet