Full lesson preview

Minimum Window Substring with Character Frequencies

Find the smallest substring of s that contains all characters of t (including multiplicity) using sliding window frequency counts.

Python practice16 minStrings – Sliding Window & FrequencyIntermediateLast updated March 25, 2026

Problem statement

Given two strings s and t, return the smallest substring of s that contains all the characters in t (including duplicates). If there is no such substring, return an empty string. If t is empty or s is empty, return an empty string. Aim for O(n) time using a sliding window approach.

Task

Apply variable-size sliding window with character frequency tracking to extract the minimum substring covering all characters of a pattern.

Examples

Classic example

Input

s = "ADOBECODEBANC", t = "ABC"

Output

"BANC"

"BANC" is the shortest substring of s that contains 'A','B','C'.

Input format

Two string arguments: s (text) and t (pattern). Example: min_window("ADOBECODEBANC", "ABC")

Output format

A string representing the minimum window substring, or an empty string if none exists.

Constraints

0 <= len(s), len(t) <= 10^5. Characters are ASCII by default. Aim for O(n) time and O(k) space where k is number of distinct characters in t.

Samples

Sample 1

Input

s = "a", t = "a"

Output

"a"

The single character matches.