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 W.

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".