Full lesson preview

Minimum Window Substring with Expanding and Shrinking Window

Find the smallest substring of s that contains all characters of t (including duplicates) using a sliding-window and hashmap.

Python practice25 minTwo Pointers & Sliding WindowAdvancedLast updated March 26, 2026

Problem statement

Given two strings s and t, return the smallest substring of s that contains all the characters in t including their frequencies. If no such substring exists, return an empty string "". You must use a sliding-window technique with a hashmap to track character counts. Aim for linear time relative to len(s) (assuming hashmap operations are O(1)).

Task

Implement an optimal sliding-window solution to return the minimal window substring of s that contains all characters from t in O(n) time on average.

Examples

Classic example

Input

s = "ADOBECODEBANC", t = "ABC"

Output

"BANC"

The smallest substring of s that contains 'A', 'B', and 'C' is "BANC".

Input format

Call min_window(s, t) where s and t are strings.

Output format

Return the shortest substring of s containing all characters of t (or an empty string if none).

Constraints

0 <= len(s), len(t) <= 10^5. Characters are ASCII. Aim for O(len(s) + len(t)) time and O(1) or O(k) extra space where k is alphabet size.

Samples

Sample 1

Input

s = "a", t = "a"

Output

"a"

Single character match.