DIY: Minimum Window Subsequence

Problem statement

Given strings ss and tt, find the minimum (contiguous) substring ww of ss, so that tt is a subsequence of ww.

If there is no window in ss that covers all characters in tt, 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 ss and tt. The following is an example input:

ss = "abcdebdde"
tt = "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".

Coding exercise

For this coding exercise, you need to implement the min_window(ss, tt) function, where ss and tt are the provided strings. The function should return the minimum subsequence of tt that exists in ss.