Interview Notes Search

This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.

Dynamic Programming

Minimum Window Subsequence

hard

DESCRIPTION (inspired by Leetcode.com)

Given a source string s1 and a pattern string s2, find the shortest contiguous portion of s1 that contains s2 as a subsequence.

Return the shortest such substring. If no valid substring exists, return an empty string.

When multiple substrings of equal minimum length exist, return the one that appears first (leftmost).

Reminder: A subsequence maintains the relative order of characters but doesn't require them to be consecutive.

Example 1

Input:

s1 = "hellointerview"
s2 = "her"

Output:

"hellointer"

Explanation: We need 'h' → 'e' → 'r' in order. The shortest window containing this subsequence starts at 'h' (index 0), includes 'e' (index 1), and ends at 'r' (index 9), giving us "hellointer".

Example 2

Input:

s1 = "codingisfun"
s2 = "xyz"

Output:

""

Explanation: None of the characters 'x', 'y', or 'z' appear in s1, so no valid subsequence window exists.

Explanation

Building Intuition

Starting Simple: The Brute Force Approach

A Smarter Approach: Forward Then Backward

The Key Observation

Why Dynamic Programming?

Why Iterate Backwards Through s2?

Walkthrough

Visualization

Solution

Alternative Approaches

Two Pointers: Forward Then Backward

2D DP