Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1456.html
1456. Maximum Number of Vowels in a Substring of Given Length (Medium)
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
Solution 1. 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/
// 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;
}
};
-
class Solution { public int maxVowels(String s, int k) { int count = 0; int length = s.length(); if (k > length) return 0; for (int i = 0; i < k; i++) { if (isVowel(s.charAt(i))) count++; } int maxCount = count; for (int i = k; i < length; i++) { char prevC = s.charAt(i - k), currC = s.charAt(i); if (isVowel(prevC)) count--; if (isVowel(currC)) count++; maxCount = Math.max(maxCount, count); } return maxCount; } public boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } }
-
// OJ: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/ // 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; } };
-
class Solution: def maxVowels(self, s: str, k: int) -> int: vowels = set('aeiou') t = sum(c in vowels for c in s[:k]) ans = t for i in range(k, len(s)): t += s[i] in vowels t -= s[i - k] in vowels ans = max(ans, t) return ans