Maximum Number of Vowels in a Substring
Maximum Number of Vowels in a Substring of Given Length: return the maximum number of vowels in any substring of s with length exactly k.
- 1 <= s.length <= 10⁵
- s consists of lowercase English letters.
- 1 <= k <= s.length
Intuition
Consecutive windows of length k overlap in k-1 characters, so recounting each one wastes almost everything. Count the first window once, then slide: add the character entering on the right, subtract the one leaving on the left. Each step costs two comparisons regardless of k.
A fixed-length window with a quantity to maximise is the cleanest sliding-window signature — the phrase 'substring of given length k' is the giveaway. Once the window size is constant, the update is always the same shape: add the entering element, remove the leaving one. Same machinery as Maximum Average Subarray and Find All Anagrams in a String.
Approach
Before reading on: write two neighbouring windows of length 3 under each other and mark what actually changed. How many characters differ? Aim for O(n) rather than O(n·k).
Why recounting is quadratic
There are n - k + 1 windows and counting each from scratch costs O(k), giving O(n·k) — with n up to 10⁵ and k up to n, that is 10¹⁰ operations. But the window at position i and the window at i+1 differ by exactly two characters. Everything else is shared, so almost the entire count is being recomputed for no reason.
Build the first window, then slide
Count vowels in s[0..k-1] directly — that is the only full count you ever do. Then for each subsequent position, the new window gains s[i] and loses s[i-k]. Increment the running count if the entering character is a vowel, decrement if the leaving one was. The count is now correct for the new window in O(1), and you compare it against the best seen so far.
Fixed versus variable windows
This is a fixed-size window: k never changes, so there is no inner loop shrinking the left edge. That makes it the simplest form of the pattern — one pointer, one arithmetic update per step. Total cost is O(n) time and O(1) space. An early exit is possible when the count reaches k, since no window can beat an all-vowel one; on typical inputs it rarely fires, but it is free to add.
Solution & live demo
Common pitfalls
Recounting each window
for i in range(len(s) - k + 1):
best = max(best, sum(1 for c in s[i:i+k] if c in vowels))count += s[i] in vowels count -= s[i - k] in vowels
Correct but O(n·k), which times out at the upper constraints. The slice also allocates a new string on every iteration.
Subtracting the wrong index
count -= s[i - k + 1] in vowels
count -= s[i - k] in vowels
When s[i] enters, the window covers i-k+1 … i, so the character that just left is at i-k. Off by one here silently keeps a stale character in the count.
Forgetting to seed with the first window
count = 0 for i in range(k, len(s)):
count = sum(1 for ch in s[:k] if ch in vowels) for i in range(k, len(s)):
The slide loop starts at index k and assumes the first window is already counted. Starting from zero undercounts every window by whatever the first one contained.
Edge cases
Only one window exists; the initial count is the answer and the slide loop never runs.
The running count stays 0 and the answer is 0.
Every window scores k, which is the maximum possible.
The window is a single character; the answer is 1 if any vowel exists, else 0.
Sliding keeps the count accurate to the last window, so a late cluster is still found.