Pattern visualizer
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. Animated on: s="ADOBECODEBANC", t="ABC" — smallest window of s containing every character of t.
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]line 3
need={A:1,B:1,C:1}, required=3. left=0, formed=0. Grow right until the window covers A, B and C.
Pseudocode
1FUNCTION minWindow(s, t):2 need = how many of each character t requires, required = number of distinct characters in t3 left = 0, formed = 0, windowCounts = empty tally of characters in the window4 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 formed8 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 formed12 move left one step right13 END WHILE14 END FOR15 RETURN empty string if best length is infinite, otherwise the substring of s from best start to best end16END FUNCTION
← / → step · space play · Home restart