Amazon

2020-05-23

## 1456. Maximum Number of Vowels in a Substring of Given Length

### Question:

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:

Using similar idea as LeetCode Question 567, check if the set contains the character.

``````class Solution {
public int maxVowels(String s, int k) {
if (s.length() < k) return 0;

// Initialize the hashset
HashSet<Character> set = new HashSet<>();

int counter = 0;
int result = 0;
char[] array = s.toCharArray();
int left = 0;
int right = 0;

for (int i = 0; i < s.length(); i++) {
char curr = array[i];
if (set.contains(curr)) {
counter++;
}
if (right - left == k - 1) {
result = Math.max(counter, result);
if (set.contains(array[left])) {
counter--;
}
left++;
}
right++;
}
return result;
}
}
``````

It could also achieve with O(n) time and O(1) space.

``````// Borrow from https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/discuss/648272/Java-Straight-Forward-O(n)-time-O(1)-space
class Solution {

public boolean isVowel(char ch) {
return (ch == 'a' || ch == 'e' || ch == 'i' | ch == 'o' || ch == 'u');
}

public int maxVowels(String s, int k) {
if (s.length() < k) return 0;
int max = 0, n = s.length();
int count = 0;
for(int i = 0; i < k; i++) {
if(isVowel(s.charAt(i))) count++;
}
max = count;

for(int i = k; i < n; i++) {
// remove the contribution of the (i - k)th character which is no longer in the window
if(isVowel(s.charAt(i - k))) count--;
// add the contribution of the current character
if(isVowel(s.charAt(i))) count++;
// update max at for each window of size k
max = Math.max(max, count);
}
return max;
}
}
``````