📘

Minimum Window Substring

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 an empty string "".

Example:

Input:

ADOBECODEBANC
ABC

Output:

BANC

Reasoning:

We start by creating a frequency map of the characters in string t: A: 1, B: 1, C: 1.
Then, we iterate over string s to find the minimum window substring that contains all characters in t, using a sliding window approach to track the characters and their frequencies.
The minimum window substring is found to be BANC, which contains all characters in t with the minimum length of $4$ characters.
The final output is BANC, as it is the smallest substring of s that includes every character in t.

Constraints:

1 <= len(s), len(t) <= 10^5
s and t consist of uppercase and lowercase English letters

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘