Maximum Number of Vowels in a Substring of Given Length [Medium]
Advertisement
Problem Statement
Return the maximum number of vowel letters in any substring of length k.
Input: s="abciiidef", k=3 → Output: 3 ("iii")
Input: s="aeiou", k=2 → Output: 2
Solutions
C++
int maxVowels(string s, int k) {
string v="aeiou";
auto isV=[&](char c){return v.find(c)!=string::npos;};
int cnt=0, ans=0;
for(int i=0;i<k;i++) cnt+=isV(s[i]);
ans=cnt;
for(int i=k;i<s.size();i++){cnt+=isV(s[i])-isV(s[i-k]);ans=max(ans,cnt);}
return ans;
}
Java
public int maxVowels(String s, int k) {
Set<Character> v=Set.of('a','e','i','o','u');
int cnt=0, ans=0;
for(int i=0;i<k;i++) if(v.contains(s.charAt(i)))cnt++;
ans=cnt;
for(int i=k;i<s.length();i++){
if(v.contains(s.charAt(i)))cnt++;
if(v.contains(s.charAt(i-k)))cnt--;
ans=Math.max(ans,cnt);
}
return ans;
}
Python
def maxVowels(s: str, k: int) -> int:
vowels = set('aeiou')
cnt = sum(c in vowels for c in s[:k])
ans = cnt
for i in range(k, len(s)):
cnt += (s[i] in vowels) - (s[i-k] in vowels)
ans = max(ans, cnt)
return ans
Complexity
- Time: O(n), Space: O(1)
Advertisement