Minimum Window Substring

Hard· variable window· frequency count

Problem

Given strings s and t, return the shortest substring of s that contains every character of t, including repeated characters as many times as they appear in t. If no such window exists, return an empty string.

Examples

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

Output: "BANC"

"BANC" is the shortest window containing A, B and C.

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

Output: ""

t needs two a characters but s has only one.

Constraints

• 1 <= s.length, t.length <= 10^5
• Uppercase and lowercase English letters

Hints & approach

Hint 1

Expand the window until it covers t, then shrink it while it still does.

Hint 2

Track how many required characters are currently satisfied instead of rescanning counts.

Hint 3

Record the best window each time you are about to lose coverage by shrinking.

Approachtry the hints first

Count the characters needed from t and let missing be t's length. Move right across s; whenever it brings in a character that is still needed, decrement missing, and always decrement that character's need count. When missing hits zero, move left forward while the left character is surplus (its need count is negative), then record the window. Finally release the left character, incrementing its need and missing, and continue expanding.

Time O(|s| + |t|) · Space O(alphabet)

← PreviousMax Consecutive Ones III Next →Subarrays with K Different Integers