Description
Given strings s1 and s2, find the minimum contiguous substring W of s1 such that s2 is a subsequence of W. Return empty string if not found.
Examples
Input:
s1 = "abcdebdde", s2 = "bde"Output:
"bcde"Explanation:
Shortest window containing 'bde' as subsequence.
Input:
s1 = "a", s2 = "a"Output:
"bcde"Explanation:
Edge case with a single character.
Input:
s1 = "jmeqksfrsdcmsiwvaovfkm", s2 = "sv"Output:
"msiv"Explanation:
The shortest substring of S containing 's' and 'v' as a subsequence is 'msiv' (from index 8 to 11), with length 4. No shorter substring contains both characters in order.
Constraints
- •
1 ≤ s1.length ≤ 2 * 10⁴ - •
1 ≤ s2.length ≤ 100