#1456
Maximum Number of Vowels in a Substring of Given Length
Medium Fixed window
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the most vowels found in any substring of length k.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the most vowels in any k-length window.
Why this works: fixed window; +1 if the new letter is a vowel, -1 if the letter leaving was one.
Example: "abciiidef", k = 3
"abc" 1, "bci" 1, "cii" 2, "iii" 3 (best)✦Hints open one at a time
Count vowels in the first window.
When sliding, add 1 if the incoming char is a vowel and subtract 1 if the outgoing char is.
↗Approach
Standard fixed-size sliding window with a running vowel count.
</>Solution (Java)
class Solution {
public int maxVowels(String s, int k) {
int count = 0, best = 0;
for (int i = 0; i < s.length(); i++) {
if (isVowel(s.charAt(i))) count++;
if (i >= k && isVowel(s.charAt(i - k))) count--; // char leaving the window
best = Math.max(best, count);
}
return best;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}!Common mistake
Using s.substring for each window, which copies k characters each time.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Sliding Window
🎬 Episode 10: video coming soon