Minimum Window SubstringHard

Minimum Window Substring

Hard 18.2k41% acceptance

Hash TableStringSliding Window

Given two strings s and t, return the smallest substring of s that contains every character of t, counting duplicates (a character that appears twice in t must appear at least twice in the window).

If no such window exists, return the empty string "". If several minimal windows tie in length, return the one with the smallest starting index.

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

"BANC" is the shortest stretch of s that contains an A, a B, and a C.

Example 2

Input: s = "a", t = "a"

Output: "a"

The whole string is the only — and therefore smallest — window.

Example 3

Input: s = "a", t = "aa"

Output: ""

s has only one "a" but t needs two, so no window qualifies.

Constraints

1 ≤ s.length ≤ 10⁵
1 ≤ t.length ≤ 10⁵
`s` and `t` consist of uppercase and lowercase English letters.

Asked atAmazonMetaGoogleMicrosoftUber

JavaScript

⌘↵ to run

Loading editor…

Case 1

"ADOBECODEBANC", "ABC"

expected: "BANC"

Case 2

"a", "a"

expected: "a"

Case 3

"a", "aa"

expected: ""

Case 4

"", "a"

expected: ""

Case 5

"ab", "b"

expected: "b"

Case 6

"aaflslflsldkalskaaa", "aaa"

expected: "aaa"

Case 7

"cabwefgewcwaefgcf", "cae"

expected: "cwae"