Minimum Window Substring

hard

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

If there is no such substring, return the empty string "". The test cases are generated so that the answer is unique.

Test Cases

Copy an input into the main harness and Run to verify

Input

s = "ADOBECODEBANC", t = "ABC"

Expected Output

"BANC"

Explanation: The minimum window "BANC" includes A, B and C from t.

Input

s = "a", t = "a"

Expected Output

"a"

Input

s = "a", t = "aa"

Expected Output

""

Explanation: Both a's from t must be in the window, but s has only one.

Constraints

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Hints

Hint 1 — click to reveal

Grow the window until it is valid, then shrink from the left while it stays valid.

Hint 2 — click to reveal

Track how many distinct characters are fully satisfied rather than rescanning the counts each time.

Java Compiler