Problem
Given a string s and an integer k, return the maximum number of vowels in any substring of s with length k.The vowels are
a, e, i, o, and u.
Example(s)
Consider the following example(s) to understand the expected input and output.Example 1
Input
s = "abciiidef"
k = 3Output
3Example 2
Input
s = "leetcode"
k = 3Output
2Solution
This solution uses the Sliding Window technique. We maintain a window of exactlyk characters and keep track of the number of vowels inside the current window. First, we count the vowels in the first
k characters and use this as the initial window count. We then slide the window one character at a time. When the window moves, we remove the character leaving the window and add the new character entering the window. If either character is a vowel, we update the vowel count accordingly.
After each shift, we update the maximum vowel count found so far.
class Solution {
public int maxVowels(String s, int k) {
int count = 0;
int max = 0;
for (int i = 0; i < k; i++) {
if (isVowel(s.charAt(i))) {
count++;
}
}
max = count;
for (int i = k; i < s.length(); i++) {
if (isVowel(s.charAt(i - k))) {
count--;
}
if (isVowel(s.charAt(i))) {
count++;
}
max = Math.max(max, count);
}
return max;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}Complexity
Each character enters and leaves the sliding window at most once, so the time complexity isO(n), where n is the length of the string. The solution uses only a few variables to maintain the window, so the extra space complexity is
O(1).