[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.