---
title: 'Minimum Window Subsequence | DP | Hard'
source: 'https://youtube.com/watch?v=r5fooD_Fxkg'
video_id: 'r5fooD_Fxkg'
date: 2026-08-04
duration_sec: 107
---

# Minimum Window Subsequence | DP | Hard

> Source: [Minimum Window Subsequence | DP | Hard](https://youtube.com/watch?v=r5fooD_Fxkg)

## Summary

This video explains how to solve the 'Minimum Window Subsequence' problem, a hard dynamic programming challenge. The presenter demonstrates an efficient two-pointer approach that finds the shortest substring in S1 containing S2 as a subsequence, reducing time complexity from cubic to O(M*N).

### Key Points

- **Problem Definition** [00:01] — The goal is to find the shortest window inside S1 that contains S2 as a subsequence, meaning letters of S2 must appear in S1 in order but not necessarily adjacent.
- **Brute Force Limitation** [00:14] — The brute force approach tries every substring of S1 and checks if S2 fits inside, resulting in cubic time complexity, which is too slow.
- **Two-Pointer Strategy** [00:27] — Use two pointers: pointer I walks through S1, and pointer J tracks how far we've matched into S2. When S1[I] equals S2[J], we make progress on a partial match.
- **DP Array for Start Indices** [00:41] — A DP array stores the index in S1 where the match for S2 up to position J begins. This remembers where the current match started.
- **Two Cases in DP Transition** [00:57] — Case 1: When the first letter of S2 matches, start a fresh window (DP[0] = I). Case 2: When a later letter matches, inherit the start from the previous step (DP[J] = DP[J-1]).
- **Tracing the Algorithm** [01:12] — Scan S1, mark the start on first match, extend the match on subsequent matches, and carry the start forward. When the full match completes, compute window length as I - DP[end] + 1.
- **Finding the Shortest Window** [01:26] — After finding a complete match, continue scanning because a later starting point could yield a shorter window. The algorithm does one pass through S1 with constant work per character.
- **Complexity and Resource** [01:41] — Total time complexity is O(M*N), and the shortest valid window is found. For more breakdowns, visit hellointerview.com (link in bio).

### Conclusion

The video presents a clear, efficient solution to the Minimum Window Subsequence problem using a DP array and two pointers, achieving O(M*N) time complexity. It emphasizes the importance of continuing the scan to ensure the shortest window is found.

## Transcript

problem, but once you see the trick, it actually becomes pretty easy. See, to find the shortest window inside S1 that contains S2 as a subsequence. So, the letters of S2 must appear in S1 in
order, but they do not have to be next to each other. The brute force is to try every substring of S1 and to check if S2 fits inside. That's cubic time, which is of course way too slow. So, here's the better idea. We use two pointers.
Pointer I walks through S1 and pointer J tracks how far we have matched into S2. Every time S1 at I equals S2 at J, we make a little progress on a partial match. We only need to remember one thing, where the match started. So, DP
of J stores the index in S1 where our match for S2 up to position J begin. There are only two cases. Case one is when the first letter of S2 matches, we begin a fresh window. DP at zero becomes I. Case two is when a later letter of S2
matches, we inherit the start from the step before. DP at J equals DP at J minus one. The same window that built S2 up to J minus one now reaches one letter further. Let us trace it. We scan S1 and hit our first B. Mark the start, then a
D, which extends the match. So, we carry the start forward. Then we reach E and the full match completes. The window length is just I minus DP at the end plus one. We have this as our best window, but we don't stop here. A later
starting point could give us a shorter window. So, we keep scanning, and we seen. That's the whole algorithm. One pass through S1 with constant work per character. The total time is O of M times N, and the shortest valid window
breakdowns, head over to hellointerview.com. Link is in our bio.