Data Structures & Algorithms · Sliding Window

Minimum Window Substring: The Expand-then-Contract Sliding Window

Q: Why is Minimum Window Substring O(n) and not O(n²)?

Because each of the two pointers only ever moves forward. The right pointer r scans the string once to expand the window, and the left pointer l scans it once to contract. Even though contraction lives inside a nested while loop, l can advance at most n times total across the entire run, so the combined work is bounded by 2n pointer moves. The formed counter is what avoids re-scanning the window on every step — it reports validity in O(1) instead of O(k).

Q: What does the formed variable actually track?

formed counts how many distinct required characters currently have enough copies inside the window. required is the total number of distinct characters in t. The window is valid — it contains all of t with correct multiplicities — precisely when formed === required. Incrementing happens only when adding a character raises its window count to exactly the target count; decrementing happens only when removing a character drops it below target. This single integer replaces an expensive map-versus-map comparison.

Q: How does the algorithm handle duplicate characters in the target?

Through the frequency maps. targetMap records how many of each character t needs (for t = "AABC", that's A: 2, B: 1, C: 1), and windowMap records how many the window currently holds. A character only counts toward formed when its window count equals its target count, so a window with a single A never satisfies a target needing two. That count-based check is why a plain set of characters would be wrong here.

Q: When should I use expand-then-contract instead of a fixed-size window?

Use it whenever the window size is unknown and you're minimizing (or the constraint is a "contains all of X" condition rather than "exactly k elements"). Fixed-size windows work when the length is given up front — like a maximum sum of k consecutive elements. Minimum Window Substring has no fixed length: the answer could be 4 characters or 400, so you grow until valid and shrink to find the tightest fit. The variable-size expand-then-contract pattern is the right tool any time validity is a threshold you cross and re-cross.

The optimal O(n) sliding window solution to Minimum Window Substring — intuition, JavaScript code, a worked walkthrough, complexity analysis, and common mistakes.

July 17, 20267 min readBy Bhavesh Singh

sliding windowstringshash maptwo pointersleetcode hard

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the Minimum Window Substring visualizer

Minimum Window Substring is where the sliding window pattern stops being cute. Most window problems ask for the longest something and grow greedily. This one asks for the smallest substring that covers a target — which means the window has to grow until it's valid, then aggressively shrink to find the tightest fit, over and over.

The trick that makes it O(n) instead of O(n²) is a single counter — formed — that answers "is my window valid right now?" in constant time, without ever rescanning the window. Get that counter right and a problem rated Hard collapses into two pointers and a frequency map.

The problem

Given two strings s and t, return the shortest substring of s that contains every character of t, including duplicates. If no such window exists, return "". The answer, when it exists, is unique.

"Including duplicates" is the detail that trips people. If t = "AABC", a valid window needs two A's, not one.

text

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

// "BANC" contains A, B, and C, and no shorter substring of s does.
// Note "ADOBEC" also contains all three — but it's length 6, and "BANC" is length 4.

The output being a substring (contiguous) is what makes a window work: valid answers are always a single [left, right] range, never scattered picks.

The brute force baseline

The literal reading: try every substring, check each one against t.

javascript

function minWindow(s, t) {
  const need = countChars(t);
  let best = "";

  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j + 1);
      if (covers(sub, need) && (best === "" || sub.length < best.length)) {
        best = sub;
      }
    }
  }
  return best;
}

There are O(n²) substrings, and covers re-counts characters in O(n) each time — O(n³) if you're naive, O(n²) if you count incrementally. Either way you're recomputing the same overlapping frequency information again and again. Every time the outer loop advances, you throw away everything the previous window taught you and rebuild from scratch.

The key insight: one window, two moves

Instead of restarting, keep one window defined by two pointers, l and r, and only ever move them forward. Two rules drive the whole algorithm:

Expand by moving r right whenever the window is not yet valid — you need more characters.
Contract by moving l right whenever the window is valid — try to make it smaller while it stays valid.

The hard part is checking validity cheaply. Comparing two frequency maps on every step would be O(alphabet) per step. So track a single integer instead:

required = the number of distinct characters in t.
formed = how many of those distinct characters currently have enough copies inside the window.

The window is valid exactly when formed === required. Updating formed costs O(1): when adding a character pushes its window count up to exactly what the target needs, formed++; when removing a character drops its count below the target, formed--. No rescanning, ever.

The optimal solution

This is the exact algorithm the visualizer animates, variable names and all.

javascript

function minWindow(s, t) {
  if (s.length === 0 || t.length === 0) return "";

  // 1. Target frequency map
  const targetMap = new Map();
  for (let char of t) {
    targetMap.set(char, (targetMap.get(char) || 0) + 1);
  }
  let required = targetMap.size;

  // 2. Window state
  let l = 0, r = 0, formed = 0;
  const windowMap = new Map();
  let ansLength = -1, ansLeft = 0, ansRight = 0;

  // 3. Expand window by moving right pointer
  while (r < s.length) {
    let char = s[r];
    windowMap.set(char, (windowMap.get(char) || 0) + 1);

    if (targetMap.has(char) && windowMap.get(char) === targetMap.get(char)) {
      formed++; // this character's requirement is now fully met
    }

    // 4. Contract from the left while the window stays valid
    while (l <= r && formed === required) {
      char = s[l];

      if (ansLength === -1 || r - l + 1 < ansLength) {
        ansLength = r - l + 1;
        ansLeft = l;
        ansRight = r;
      }

      windowMap.set(char, windowMap.get(char) - 1);
      if (targetMap.has(char) && windowMap.get(char) < targetMap.get(char)) {
        formed--; // dropped below the requirement — window is invalid again
      }
      l++;
    }
    r++;
  }

  return ansLength === -1 ? "" : s.substring(ansLeft, ansRight + 1);
}

Two comparisons are load-bearing. The === targetMap.get(char) on expand fires formed++ exactly once per character requirement — using >= would over-count and break formed. The < targetMap.get(char) on contract fires formed-- only when you've genuinely lost a required copy — excess characters can leave the window with no effect on validity, which is what lets the window contract past padding like the D, O, E in "ADOBEC".

Walkthrough

Trace s = "AXBXAB", t = "AB". Target map is {A: 1, B: 1}, so required = 2. Watch formed gate every contraction.

r	Move	char	windowMap (live)	formed / required	Valid?	Action	Best
0	expand	A	{A:1}	1 / 2	no	need more	—
1	expand	X	{A:1, X:1}	1 / 2	no	X isn't in t	—
2	expand	B	{A:1, X:1, B:1}	2 / 2	yes	enter contract	—
2	contract	—	—	2 / 2	yes	record [0,2] `"AXB"` len 3	AXB
2	contract	A	remove s[0]=A → {A:0}	1 / 2	no	A dropped below 1, l→1	AXB
3	expand	X	{A:0, X:2, B:1}	1 / 2	no	still short an A	AXB
4	expand	A	{A:1, X:2, B:1}	2 / 2	yes	enter contract	AXB
4	contract	X	remove s[1]=X → {X:1}	2 / 2	yes	[1,4] len 4 not smaller; X is excess, stays valid	AXB
4	contract	B	remove s[2]=B → {B:0}	1 / 2	no	B dropped below 1, l→3	AXB
5	expand	B	{A:1, X:1, B:1}	2 / 2	yes	enter contract	AXB
5	contract	X	remove s[3]=X → {X:0}	2 / 2	yes	X excess, stays valid; window [4,5] len 2	AXB
5	contract	A	window [4,5] `"AB"` len 2 < 3 → record; then remove s[4]=A	1 / 2	no	new best, l→5	AB

r walks off the end and the loop ends. ansLength = 2, so the answer is s.substring(4, 6) = "AB".

The two contraction rows at r = 4 and r = 5 show the payoff: removing X keeps formed at 2 because X was never required, so the window keeps shrinking for free until it hits an actually-needed character. That's how it finds the tight "AB" instead of settling for the first valid "AXB".

Complexity

Approach	Time	Space	Why
Brute force	O(n²)	O(n)	every substring, incremental counting
Sliding window	O(n)	O(k)	each pointer crosses the string once; maps hold ≤ k distinct chars

Each character is added exactly once (by r) and removed at most once (by l), so total work is 2n pointer moves — O(n) where n = s.length. The maps store at most k distinct characters, where k is the size of t's alphabet, giving O(k) space — which is O(1) for a fixed alphabet like uppercase English letters.

The inner while never makes it worse than linear: l only ever advances, so across the entire run it moves a grand total of n steps, no matter how many times the inner loop restarts.

Common mistakes

Using >= when bumping formed. formed++ must fire only on the exact transition to the required count. With >=, a third A in the window when you need one would increment formed again, and the counter loses all meaning.
Forgetting duplicates in t. required is the number of distinct characters, but validity depends on counts. A window with one A does not satisfy t = "AAB". The frequency maps handle this automatically — a single Set would not.
Contracting on <= instead of <. Removing an excess character (window count still ≥ target) must not decrement formed. Use windowMap.get(char) < targetMap.get(char) so the window can shed padding while staying valid.
Recording the answer after l++. Capture [l, r] and its length before you shrink the window; once you've moved l, the range you measured is gone.
Returning the length instead of the substring. The problem wants the actual window text. Track ansLeft/ansRight and slice at the end — storing only ansLength throws away the position.

Where this pattern shows up next

Expand-then-contract with an O(1) validity counter is the template for every "smallest window covering a constraint" problem — minimum window with a character-count target, shortest subarray with a required sum, smallest range covering all lists. Once formed === required clicks, you'll reach for it reflexively.

The fastest way to internalize the two-pointer dance is to watch it move. Step through the Minimum Window Substring visualizer to see the window expand, the formed counter tick up, and the frame squeeze inward one character at a time — including the moment "AXB" gets beaten by "BANC" on the full "ADOBECODEBANC" input.

FAQ

Why is Minimum Window Substring O(n) and not O(n²)?

Because each of the two pointers only ever moves forward. The right pointer r scans the string once to expand the window, and the left pointer l scans it once to contract. Even though contraction lives inside a nested while loop, l can advance at most n times total across the entire run, so the combined work is bounded by 2n pointer moves. The formed counter is what avoids re-scanning the window on every step — it reports validity in O(1) instead of O(k).

What does the `formed` variable actually track?

formed counts how many distinct required characters currently have enough copies inside the window. required is the total number of distinct characters in t. The window is valid — it contains all of t with correct multiplicities — precisely when formed === required. Incrementing happens only when adding a character raises its window count to exactly the target count; decrementing happens only when removing a character drops it below target. This single integer replaces an expensive map-versus-map comparison.

How does the algorithm handle duplicate characters in the target?

Through the frequency maps. targetMap records how many of each character t needs (for t = "AABC", that's A: 2, B: 1, C: 1), and windowMap records how many the window currently holds. A character only counts toward formed when its window count equals its target count, so a window with a single A never satisfies a target needing two. That count-based check is why a plain set of characters would be wrong here.

When should I use expand-then-contract instead of a fixed-size window?

Use it whenever the window size is unknown and you're minimizing (or the constraint is a "contains all of X" condition rather than "exactly k elements"). Fixed-size windows work when the length is given up front — like a maximum sum of k consecutive elements. Minimum Window Substring has no fixed length: the answer could be 4 characters or 400, so you grow until valid and shrink to find the tightest fit. The variable-size expand-then-contract pattern is the right tool any time validity is a threshold you cross and re-cross.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the Minimum Window Substring visualizer

The problem#

The brute force baseline#

The key insight: one window, two moves#

The optimal solution#

Walkthrough#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

Why is Minimum Window Substring O(n) and not O(n²)?#

What does the formed variable actually track?#

How does the algorithm handle duplicate characters in the target?#

When should I use expand-then-contract instead of a fixed-size window?#

Related articles