Problem Statement
Maximum Number of Vowels in a Substring of Given Length
You are given a string s and a number k. Your job is to look at every chunk of the string that is exactly k letters long, and find the chunk with the most vowels. Vowels are the letters 'a', 'e', 'i', 'o', 'u'. The answer is that biggest vowel count. A "chunk of k letters in a row" is called a substring of length k. The trick that makes this fast is a sliding window. A sliding window is like a small picture frame that holds exactly k letters at a time. You start the frame at the left end of the string, then slide it one step to the right over and over until it reaches the end. Instead of recounting the vowels inside the frame every time you move it, you only adjust for the one letter that just came into the frame and the one letter that just fell out of it. That small adjustment is what makes this quick.
Signals to notice
Brute force first
For each window count vowels — O(nk).
The key insight
Sliding window: maintain vowel count. +1 if entering char is vowel, -1 if leaving char is vowel. Track max. O(n).
Trace it on s="abciiidef", k=3
init window [a,b,c]: count=1 (a), max_count=1 i=3: +s[3]='i', -s[0]='a' -> count=1, max=1 i=4: +s[4]='i', -s[1]='b'(no) -> count=2, max=2 i=5: +s[5]='i', -s[2]='c'(no) -> count=3, max=3 i=6: s[6]='d'(no), -s[3]='i' -> count=2, max=3 i=7: +s[7]='e', -s[4]='i' -> count=2, max=3 i=8: s[8]='f'(no), -s[5]='i' -> count=1, max=3 return max_count = 3
What must stay true
Vowel count updates in O(1) per slide. Never recount the whole window.
Shape of the loop
count = vowels in s[0..k)
maxCount = count
for i from k to len(s)-1:
count += isVowel(s[i]) - isVowel(s[i-k]) # enter - leave
maxCount = max(maxCount, count)
return maxCountPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Recounting each window — update incrementally.