DSA problem

Minimum Window Substring

HardSliding Window - Dynamic SizePattern: Variable-Size Sliding Windowtop75FreeAmazonGoogleMetaMicrosoftUber

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 such that the answer is unique.

A substring is a contiguous, non-empty sequence of characters. The goal is to find the shortest contiguous segment of s that covers every required character of t with the correct multiplicity. The optimal approach uses a variable-size sliding window: expand the right edge until the window is valid, then shrink the left edge as far as possible while it stays valid, recording the smallest valid window seen.

Examples

Example 1

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

Output: "BANC"

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

Example 2

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

Output: "a"

Explanation: The entire string s is the minimum window.

Example 3

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

Output: ""

Explanation: Both characters "a" from t must be included in the window. Since the largest window of s has only one "a", return the empty string.

Constraints

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

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowhash-tablestringtwo-pointers

Browse all DSA problems