Minimum Window Subsequence
Hard · Sliding Window · String · Dynamic Programming · Sliding Window · Two Pointers
Problem
Given strings s1 and s2, find the shortest contiguous substring of s1 that contains s2 as a subsequence. A subsequence keeps the characters of s2 in order but does not need them to be next to each other.
Return that substring. If several shortest windows exist, return the one that starts furthest left. If no window works, return the empty string "".
Examples
Input: s1 = "axbxcab", s2 = "ab" Output: "ab"
"axb" contains a then b, but the window "ab" at the end is shorter.
Input: s1 = "abab", s2 = "ab" Output: "ab"
Windows at index 0 and 2 both have length 2, so the leftmost wins.
Input: s1 = "xyz", s2 = "zx" Output: ""
No x comes after the z, so no window exists.
Constraints
- 1 <= s1.length <= 2 * 10^4
- 1 <= s2.length <= 100
- s1 and s2 consist of lowercase English letters
Approaches
- Baseline: earliest end from every start — time O(n²), space O(1)
Follow-up
The forward-then-backward scan finds every minimal window, which is more than the shortest one: it also tells you, for every end, how far left a valid window can start. The use cases count all valid windows and ask whether one fits a length limit.
Related problems
Start free on Cariara · Coding problems · System design studio
