dsa · hard

Minimum Window Substring

Given strings s and t, return the **shortest** substring of s that covers every character of t (including duplicates). If none exists, return the empty string. If several windows have the same length, return the left-most one.

Arguments

• s — the haystack string
• t — characters (with multiplicity) the window must cover

Example

s = "ADOBECODEBANC", t = "ABC" → "BANC" (length 4; ADOBEC is longer).

s = "a", t = "a" → "a".

s = "a", t = "aa" → "" because s has only one a.

Constraints

1 <= s.length <= 10^5 1 <= t.length <= 10^5 s and t consist of uppercase and lowercase English letters Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
"ADOBECODEBANC"
"ABC"

Expected:
BANC

Example 2

Input:
"a"
"a"

Expected:
a

Example 3

Input:
"a"
"aa"

Expected:

Open in the Dojo editor