Shortest Window Holding a Sequence
HardTwo Pointers
Problem
A log analyst wants the shortest contiguous stretch of a log string s that contains the event code t as a subsequence (the letters of t in order, not necessarily adjacent).
Return that substring. If several have the same minimum length, return the one that starts leftmost. If none exists, return the empty string.
Example 1
- Input:
- s = "abcdebdde", t = "bde"
- Output:
- "bcde"
"bcde" and "bdde" both have length 4; "bcde" starts first.
Example 2
- Input:
- s = "xyz", t = "q"
- Output:
- ""
Example 3
- Input:
- s = "babab", t = "bb"
- Output:
- "bab"
Constraints
- 1 ≤ s.length ≤ 2·10^4
- 1 ≤ t.length ≤ 100
- s and t consist of lowercase English letters
Hint
Show the first hint
Scan s forward matching t greedily. Where the match completes, you know a window ends. Where should it start?
Walkthrough
How to approach it
01Clarify before coding
- Subsequence or substring? t must appear in order inside the window, not necessarily contiguously.
- Ties? The leftmost window wins.
- No match? Return the empty string.
02Brute force
For every start index, scan forward greedily until t is matched and record the window.
Cost: O(n² ) in the worst case (each start may scan to the end), about 4·10^8 for n = 2·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.