Minimum Window Substring

Given strings s and t, return the shortest substring of s that contains every character of t, repeats included: if t has two as, the window needs at least two. Upper and lower case are different characters.

If several windows are equally short, return the one that starts first. If there is none, return the empty string "".

Constraints

  • 1 ≤ length of s ≤ 50,000
  • 1 ≤ length of t ≤ 5,000
  • s and t have English letters only.

Example 1

Input
s = "ADOBECODEBANC"
t = "ABC"
Output
"BANC"
Why:

BANC holds an A, a B and a C, and no shorter stretch does.

Example 2

Input
s = "a"
t = "aa"
Output
""
Why:

t needs two as and s has only one.

Example 3

Input
s = "abcab"
t = "ab"
Output
"ab"
Why:

ab, ba and ab are all shortest; the first one wins.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –