Sliding window over a string

The idea: a window that only slides right

Many string questions ask for the best substring with some property: the longest one without a repeated letter, the shortest one that holds every letter of a word. Checking every substring costs O(n²) substrings. A sliding window does it in one pass. Two pointers L and R mark the window s[L, R): R grows it by taking the next letter in, L shrinks it by dropping the first letter. Neither pointer ever moves back.

Counts make each move O(1)

The window keeps a count of each letter inside it. Growing adds 1 to one count, shrinking takes 1 away. The rule of the problem is read off the counts: a count above 1 means a repeat; the number of non-zero counts is the number of distinct letters; comparing with the counts of a target word tells whether the window covers it. On the canvas each move is three steps: the pointer moves, a +x or −x box flies to the count, and the rule is checked.

Four problems, one template

problem	valid when	next move	page input → answer
longest without repeats	no count above 1	invalid → shrink, else grow	abcabcbb → "abc"; pwwkew → "wke"
longest with at most K distinct	non-zero counts ≤ K	invalid → shrink, else grow	ccaabbb, K = 2 → "aabbb"
minimum window covering T	count ≥ need for every letter of T	valid → shrink, else grow	ADOBECODEBANC, T = ABC → "BANC"
all anagrams of p	length |p| and counts = p's	length |p| → shrink, else grow	cbaebabacd, p = abc → 0, 6

In pwwkew the window "pw" takes the second w and becomes invalid. L drops p, still invalid, then drops the first w: only then is the window "w" valid again, and it grows to "wke". (Demo: pwwkew) The anagram window has a fixed size: once it holds |p| letters it drops one and takes one, so it just slides. (Demo: anagrams of abc)

Longest or shortest: when to shrink

For a longest valid window, shrink only while the window breaks the rule; every valid window is a candidate. This works because the rule is monotone: if a window is valid, so is every window inside it. For a shortest valid window, shrink while the window still holds, recording it each time; when it stops holding, grow again. In ADOBECODEBANC the first window that covers A, B, C is "ADOBEC" (length 6); the scan ends with "BANC" (length 4). (Demo: minimum window) In BANANA there is no C, so the window grows to the end and never becomes valid: the answer is empty. (Demo: no window exists)

Why it is O(n)

R moves at most n times and L at most n times, and each move costs O(1). So a whole scan is at most 2n moves. On abcabcbb that is 8 + 7 = 15 moves, against 8 · 9 / 2 = 36 substrings for brute force; the gap grows like n against n². The counts take O(alphabet size) memory. (Demo: longest without repeats)

input	answer	R moves	L moves
abcabcbb	"abc", s[0, 3)	8	7
pwwkew	"wke", s[2, 5)	6	3
ccaabbb, K = 2	"aabbb", s[2, 7)	7	2
ADOBECODEBANC, T = ABC	"BANC", s[9, 13)	13	10
BANANA, T = ABC	none	6	0
cbaebabacd, p = abc	starts 0, 6	10	8

Related pages

Rabin-Karp slides a fixed window too, but keeps a rolling hash instead of counts. KMP finds one exact pattern without moving back in the text. LZ77 and DEFLATE search a sliding window of past text for repeats, and Rate Limit Windows uses sliding windows over time.

What the page leaves out

Inputs are short fixed samples. The page leaves out the jump trick for repeats (store each letter's last index and move L past it in one go), a "formed" counter that avoids re-checking all letters of T, windows over numbers (sums, products, monotonic-deque maximum), and problems where the rule is not monotone, which a sliding window cannot solve.

References

Minimum Window Substring (LeetCode 76)

Longest Substring Without Repeating Characters (LeetCode 3)

Find All Anagrams in a String (LeetCode 438)