Maximum Number of Vowels in a Substring of Given Length
Find the most vowels in any substring of length k with a fixed-size sliding window that updates its vowel count in O(1) per step.
Problem Understanding
Maximum Number of Vowels in a Substring of Given Length (LeetCode 1456): given a string s of lowercase letters and an integer k, return the maximum number of vowels (a, e, i, o, u) in any substring of s of length k.
Examples: "abciiidef", k = 3 → 3 ("iii"); "aeiou", k = 2 → 2; "leetcode", k = 3 → 2.
The Intuition: Only the Edges Change
Slide a window of k letters one step to the right and k - 1 letters stay put. Only two things change: one letter enters on the right and one leaves on the left.
- Count the first window.
- Slide: +1 if the entering letter is a vowel, -1 if the leaving one is.
- Keep the best count.
It is the fixed-size window from Fixed-Length Sliding Window, with "is a vowel" as the thing being counted.
Interactive Walkthrough
k = 3 · O(1) PER SLIDE
FIRST WINDOW
s (window of 3 outlined, v = vowel)
lo hi
0 v
1
2
3 v
4 v
5 v
6
7 v
8
count
1
best
0
Build the first window: 'a' is a vowel, count = 1
Next
Build the first window: 'b' is not a vowel, count stays 1
s
k
The outlined cells are the window. The letter entering is filled and the one leaving is red; vowels are marked with a v under their index. Try Example 5 to see y treated as a consonant.
Dry Run Table
Input: s = "abciiidef", k = 3.
| Window | In | Out | count | best |
|---|---|---|---|---|
| abc | 1 | 1 | ||
| bci | i (+1) | a (−1) | 1 | 1 |
| cii | i (+1) | b | 2 | 2 |
| iii | i (+1) | c | 3 | 3 |
| iid | d | i (−1) | 2 | 3 |
| ide | e (+1) | i (−1) | 2 | 3 |
| def | f | i (−1) | 1 | 3 |
Answer: 3.
The Solution Template
Count the first window, then one O(1) update per slide.
Maximum Number of Vowels in a Substring of Given Length Code
1var maxVowels = function(s, k) {2 const vowels = new Set('aeiou');3 let count = 0;4 for (let i = 0; i < k; i++) count += vowels.has(s[i]) ? 1 : 0;5 let best = count;6 for (let i = k; i < s.length; i++) {7 count += (vowels.has(s[i]) ? 1 : 0) - (vowels.has(s[i - k]) ? 1 : 0);8 best = Math.max(best, count);9 }10 return best;11};
Edge Cases & Common Mistakes
- k equals the length of s: there is only the first window.
- Off-by-one on the leaving letter: it is s[i - k], not s[i - k + 1].
- Recounting each window: O(n · k), too slow for k near 10^5.
- Counting y: it is not a vowel in this problem.
Summary
Count vowels in the first k letters, then slide: add the entering letter, subtract the leaving one, and keep the best. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet