All problems

Minimum Window Substring

Hard · sliding window

You are given two strings, s and t. Find the shortest substring of s that contains every character of t, counting repeats: if t has two "a" characters, the substring needs at least two "a" characters too. The substring may contain extra characters that are not in t. A substring is a run of neighbouring characters, and letters are case sensitive ("a" and "A" are different).

If several substrings share the shortest length, return the one that starts earliest in s. If no substring of s covers t, return the empty string "".

Examples

Example 1

Input: s = "bbaacbab", t = "abc"

Output: "acb"

The shortest run that holds an a, a b and a c is "acb" (length 3). No run of length 2 can hold three letters.

Example 2

Input: s = "aabcab", t = "aab"

Output: "aab"

The substring needs two a characters and one b. "aab" at the start does, and no shorter run holds two a characters and a b.

Example 3

Input: s = "abc", t = "d"

Output: ""

There is no d anywhere in s, so nothing covers t.

Constraints