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
Solution: Sliding Window
Keep tracking the number of vows in a window of size k.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int maxVowels(string s, int k) { vector<int> v(128); v['a'] = v['e'] = v['i'] = v['o'] = v['u'] = 1; int total = 0; int ans = 0; for (int i = 1; i <= s.length(); ++i) { total += v[s[i - 1]]; if (i >= k) { ans = max(ans, total); total -= v[s[i - k]]; } } return ans; } }; |