Maximum Number of Vowels in a Substring of Given Length
Leetcode Daily Challenge (5th May, 2023)
Problem Statement:-
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'.
Link: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/
Problem Explanation with examples:-
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.
Constraints
1 <= s.length <= 10<sup>5</sup>sconsists of lowercase English letters.1 <= k <= s.length
Intuition:-
We will use a sliding window of size k to find the maximum number of vowels in a substring of size k.
At each step, we will add the vowel count of the current character and subtract the vowel count of the first character of the previous window.
We will keep track of the maximum vowel count and return it in the end.
Solution:-
Initialize a variable to store the vowel count of the current window.
Iterate over the first k characters of the string and add the vowel count of each character to the variable.
Initialize a variable to store the maximum vowel count and store the vowel count of the current window in it.
Iterate over the remaining characters of the string. Subtract the vowel count of the first character of the previous window from the variable. Add the vowel count of the current character to the variable.
Update the maximum vowel count if the vowel count of the current window is greater than it.
Return the maximum vowel count.
Code:-
JAVA Solution
class Solution {
public int maxVowels(String s, int k) {
String v = "aeiou";
int c = 0;
int n = s.length();
for (int i = 0; i < k; i++) {
if (v.indexOf(s.charAt(i)) != -1) {
c++;
}
}
int mx = c;
for (int i = k; i < n; i++) {
if (v.indexOf(s.charAt(i-k)) != -1) {
c--;
}
if (v.indexOf(s.charAt(i)) != -1) {
c++;
}
mx = Math.max(mx, c);
}
return mx;
}
}
Python Solution
class Solution:
def maxVowels(self, s: str, k: int) -> int:
v = 'aeiou'
c = 0
n = len(s)
for i in range(k):
if s[i] in v:
c += 1
mx = c
for i in range(k,n):
if s[i-k] in v:
c -= 1
if s[i] in v:
c += 1
mx = max(mx,c)
return mx
Complexity Analysis:-
TIME:-
The time complexity is O(n) where n is the length of the string. We iterate over the string once and perform constant time operations at each step.
SPACE:-
The space complexity is O(1) as we use constant extra space.