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, u).
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.
Example 4:
Input: s = "rhythms", k = 4 Output: 0 Explanation: We can see that s doesn't have any vowel letters.
Example 5:
Input: s = "tryhard", k = 4 Output: 1
Constraints:
1 <= s.length <= 10^5
s
consists of lowercase English letters.1 <= k <= s.length
Related Topics:
String, Sliding Window
We keep a sliding window of size k
. Let i
be the index of the new element getting into the window. We increment cnt
if s[i]
is vowel.
If i >= k
, we need to pop s[i - k]
out of the window and decrement cnt
if s[i - k]
is vowel. The answer is the maximum cnt
.
// OJ: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
public:
int maxVowels(string s, int k) {
int cnt = 0, ans = 0;
for (int i = 0; i < s.size(); ++i) {
if (i >= k) cnt -= isVowel(s[i - k]);
cnt += isVowel(s[i]);
ans = max(ans, cnt);
}
return ans;
}
};