hardDynamic Programming 2DAI-applied~45 min
Smallest Prompt Window Containing Required Tokens In Order
A guardrail must confirm that a long generated transcript contains a required token sequence in order (not necessarily contiguous). To highlight the evidence, find the shortest contiguous window of the transcript that still contains the required sequence as a subsequence.
Problem
Given strings s and t, return the minimum-length contiguous substring of s such that t is a subsequence of it. If no such window exists, return the empty string. If several windows tie, return the leftmost.
Input
Two strings s and t.
Output
The smallest qualifying substring of s, or an empty string.
Constraints
- 1 ≤ |s| ≤ 2e4
- 1 ≤ |t| ≤ 100
- Lowercase English letters.
Examples
Example 1
Input
s="abcdebdde" t="bde"
Output
bcde
'bcde' contains 'bde' as a subsequence and is the shortest such window.
Example 2
Input
s="jmeqksfrsdcmsiwvaovztaqenprpvnbstl" t="u"
Output
'u' never appears, so no window exists.