The Trick to Solve Minimum Window Subsequence
44sReveals a clever two-pointer DP trick that simplifies a hard problem, appealing to coders looking for efficient solutions.
▶ Play ClipAI 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).
Chapters
[00:01]
Problem Definition
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.
[00:14]
Brute Force Limitation
The brute force approach tries every substring of S1 and checks if S2 fits inside, resulting in cubic time complexity, which is too slow.
[00:27]
Two-Pointer Strategy
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.
[00:41]
DP Array for Start Indices
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.
[00:57]
Two Cases in DP Transition
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]).
[01:12]
Tracing the Algorithm
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.
[01:26]
Finding the Shortest Window
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.
[01:41]
Complexity and Resource
Total time complexity is O(M*N), and the shortest valid window is found. For more breakdowns, visit hellointerview.com (link in bio).
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.
Mentioned in this Video
Tutorial Checklist
2
00:41
Create a DP array where DP[J] stores the start index in S1 for the match of S2 up to position J.
3
00:57
Iterate through S1 with pointer I. If S1[I] equals S2[0], set DP[0] = I. If S1[I] equals S2[J] for J>0, set DP[J] = DP[J-1].
4
01:12
When J reaches the end of S2, compute window length as I - DP[J-1] + 1 and update the best window if shorter.
Study Flashcards (7)
What is the problem statement for Minimum Window Subsequence?
easy
Click to reveal answer
What is the problem statement for Minimum Window Subsequence?
easy
Click to reveal answer
Find the shortest window in S1 that contains S2 as a subsequence, meaning letters of S2 appear in S1 in order but not necessarily adjacent.
00:01
What is the time complexity of the brute force approach?
easy
Click to reveal answer
What is the time complexity of the brute force approach?
easy
Click to reveal answer
Cubic time, O(N^3).
00:14
What does the DP array store in this algorithm?
medium
Click to reveal answer
What does the DP array store in this algorithm?
medium
Click to reveal answer
DP[J] stores the index in S1 where the match for S2 up to position J begins.
00:41
What are the two cases in the DP transition?
medium
Click to reveal answer
What are the two cases in the DP transition?
medium
Click to reveal answer
Case 1: When the first letter of S2 matches, set DP[0] = I. Case 2: When a later letter matches, set DP[J] = DP[J-1].
00:57
How do you compute the window length when a full match is found?
medium
Click to reveal answer
How do you compute the window length when a full match is found?
medium
Click to reveal answer
Window length = I - DP[end] + 1.
01:12
Why do you continue scanning after finding a complete match?
easy
Click to reveal answer
Why do you continue scanning after finding a complete match?
easy
Click to reveal answer
Because a later starting point could give a shorter window.
01:26
What is the overall time complexity of the optimal algorithm?
medium
Click to reveal answer
What is the overall time complexity of the optimal algorithm?
medium
Click to reveal answer
O(M*N), where M is length of S1 and N is length of S2.
01:41
💡 Key Takeaways
🔧
Two-Pointer Technique
Introduces an efficient alternative to brute force, reducing complexity significantly.
00:27
💡
DP Array for Start Indices
Clever use of DP to track the start of matches, enabling O(1) window length calculation.
00:41
⚖️
Continuing Scan for Shorter Windows
Emphasizes that the first complete match may not be optimal, a key insight for correctness.
01:26Full Transcript
[00:01] 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
[00:14] 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.
[00:27] 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
[00:41] 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
[00:57] 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
[01:12] 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
[01:26] 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
[01:41] breakdowns, head over to hellointerview.com. Link is in our bio.
