← Back to DSA Animator
Minimum Window Substring LC #76 Hard Variable Sliding Window · Matches Counter
Problem

Given strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included. Return "" if no such window exists.

Example
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: Minimum window containing A, B, C.
Constraints: 1 ≤ s.length, t.length ≤ 10⁵  |  s and t consist of uppercase and lowercase English letters.
Try Examples
Custom:
Approach
Variable Sliding Window + formed Counter
Expand R until all t-chars satisfied (formed==needed). Record window. Shrink L to minimize length. formed only updates when have[c] exactly reaches need[c] — avoids full map scan every step. O(n+m) time, O(m) space.
① Init
›
② Expand R →
›
③ Valid ✓
›
④ Shrink L ←
›
⑤ Done
String s
formed / needed 0 / 0
Waiting to start…
Char Frequencies — need (t) vs have (window)
charneedhave
Init
Press ▶ Play or Next Step to begin.
Best window —
Variables
L (left)
—
R (right)
—
formed
0
win len
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
—
Minimum window substring
Ready 0 / 0
Select an example and press Play.
Algorithm
1
Build need map from t. needed = unique chars in t.
2
Expand r: add s[r] to have. If have[c]==need[c] → formed++
3
When formed==needed: record window if new minimum
4
Shrink l: remove s[l] from have. If have[c]<need[c] → formed--. l++
5
Repeat until r reaches end of s
Time
O(n+m)
Space
O(m)
Why It Works

formed counter: Instead of scanning all of need every step, formed increments only when have[c] exactly reaches need[c]. One counter replaces a full map comparison.

Expand → Shrink cycle: We expand R until all chars are satisfied, then shrink L to find the minimum valid window. Two-pointer guarantees each character is visited at most twice — O(n) total.

Why variable window? Unlike fixed windows, the valid size varies. We don't know the answer length upfront — the window grows and shrinks dynamically based on the contents of t.