DSA Tracker

Visualize

Minimum Window Substring

Once a window contains every character of t, making it smaller can only help — so the instant it's valid, greedily shrink from the left and keep shrinking as long as it stays valid, recording the window size at each valid point. Because left and right each only ever move forward, this checks every window worth checking in a single pass instead of re-scanning from scratch for every starting point. Reach for it on 'smallest substring covering a set' problems.

Details

Animated on: s="ADOBECODEBANC", t="ABC" — smallest window of s containing every character of t

Problem:Minimum Window SubstringHard

Pattern:Sliding Window

Strings

step 1 / 11

A
[0]
D
[1]
O
[2]
B
[3]
E
[4]
C
[5]
O
[6]
D
[7]
E
[8]
B
[9]
A
[10]
N
[11]
C
[12]

need={A:1,B:1,C:1}, required=3. left=0, formed=0. Grow right until the window covers A, B and C.

  • left=0· arr[0] = A
Pseudocode
1FUNCTION minWindow(s, t):
2  need = how many of each character t requires, required = number of distinct characters in t
3  left = 0, formed = 0, windowCounts = empty tally of characters in the window
4  best = (infinite length, start 0, end 0)
5  FOR right from 0 to length of s - 1:
6    add 1 to windowCounts for character s[right]
7    IF s[right] is needed and its window count now equals what's needed: add 1 to formed
8    WHILE formed equals required:
9      IF right - left + 1 < best length: best = (right - left + 1, left, right)
10      subtract 1 from windowCounts for character s[left]
11      IF s[left] is needed and its window count drops below what's needed: subtract 1 from formed
12      move left one step right
13    END WHILE
14  END FOR
15  RETURN empty string if best length is infinite, otherwise the substring of s from best start to best end
16END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. need={A:1,B:1,C:1}, required=3. left=0, formed=0. Grow right until the window covers A, B and C.
  2. right=5: window [0,5]="ADOBEC" now has A,B,C all covered — formed=3=required. First valid window, len6. best=6.
  3. Shrink: drop s[0]='A' — A count falls below need, formed→2. left=1. Window no longer valid, resume growing right.
  4. right=10: chars D,O,E,B pass without completing t again, then s[10]='A' restores it — window [1,10] has A,B,C again, formed=3.
  5. Shrink repeatedly (D, O still satisfied B, E all non-critical to drop): window shrinks down to [5,10] len6 — tied with best, not smaller, so best stays 6.
  6. Drop s[5]='C' — C count falls below need, formed→2. left=6. Resume growing right.
  7. right=12: O,D,E,B,A,N pass, then s[12]='C' completes t again — window [6,12]="ODEBANC" len7, formed=3.
  8. Shrink: drop O (idx6, not needed) then D (idx7, not needed) — window [8,12]="EBANC" len5, smaller than best 6! best=5.
  9. Shrink further: drop E (idx8, not needed) — window [9,12]="BANC" len4, smaller again! best=4.
  10. Drop s[9]='B' — B count falls below need, formed→2. left=10. Right is already at the string's end — loop finishes.
  11. Return the smallest window recorded: s.slice(9,13) = "BANC" — the minimum window containing A, B and C.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Window Substring in the editorAll Strings problemsBack to roadmap