DIY: Minimum Window Subsequence

Problem statement

Given strings s and t, find the minimum (contiguous) substring w of s, so that t is a subsequence of s.

If there is no window in s that covers all characters in t, return an empty string "". If there are multiple minimum-length windows, return the one with the left-most starting index.

Input

The input will be two strings s and t. The following is an example input:

s = "abcdebdde"
t = "bde"

Output

For the above input, the output will be:

"bcde"

The strings "bcde" and "bdde" are both minimum subsequences, but "bcde" occurs before "bdde".