Sliding WindowSliding Window

Sliding Window (Frequency Map)

Slide a window over a string while a hash map tracks character counts and a "formed" counter says how many required characters are satisfied — the engine behind anagram search and minimum window substring.

Learn Sliding Window with Frequency Map →
a
a
0
a
1
b
2
a
3
c
4
b
5
e
6
b
7
e
8
b
9
e
10
freq (char:count)
1/28Longest substring with at most k=3 distinct characters. A frequency map tracks what is inside the window so "how many distinct" is just the map's size.
Current windowEntering (r)Shrunk awayBest window
PseudocodeLearn Sliding Window with Frequency Map →
1l = 0, best = 0, freq = {}
2for r in 0 .. n-1:
3  freq[s[r]] += 1
4  while len(freq) > k:
5    freq[s[l]] -= 1; if freq[s[l]] == 0: delete freq[s[l]]
6    l += 1
7  best = max(best, r - l + 1)
8return best
Variables
l0
best0
k3
distinct0
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(Σ)
Speed