1456. Maximum Number of Vowels in a Substring of Given Length
1. Description
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’.
2. Example
Example 1
Input: s = “abciiidef”, k = 3
Output: 3
Explanation: The substring “iii” contains 3 vowel letters.
Example 2
Input: s = “aeiou”, k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.
Example 3
Input: s = “leetcode”, k = 3
Output: 2
Explanation: “lee”, “eet” and “ode” contain 2 vowels.
3. Constraints
- 1 <= s.length <= $10^5$
- s consists of lowercase English letters.
- 1 <= k <= s.length
4. Solutions
Sliding Window
n = s.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int maxVowels(const string &s, int k) {
int current_vowel = 0, max_vowel = 0;
for (int i = 0; i < k; ++i) {
current_vowel += count_vowel(s[i]);
}
max_vowel = current_vowel;
for (int i = k; i < s.size(); ++i) {
current_vowel = current_vowel + count_vowel(s[i]) - count_vowel(s[i - k]);
max_vowel = max(current_vowel, max_vowel);
}
return max_vowel;
}
private:
inline int count_vowel(char c) {
switch (c) {
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return 1;
default:
return 0;
}
}
};