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 such window in S
that covers all characters in T
, return the empty string ""
. If there are multiple such minimum-length windows, return the one with the left-most starting index.
Example 1:
Input: S = "abcdebdde", T = "bde" Output: "bcde" Explanation: "bcde" is the answer because it occurs before "bdde" which has the same length. "deb" is not a smaller window because the elements of T in the window must occur in order.
Note:
<li>All the strings in the input will only contain lowercase letters.</li>
<li>The length of <code>S</code> will be in the range <code>[1, 20000]</code>.</li>
<li>The length of <code>T</code> will be in the range <code>[1, 100]</code>.</li>