Maximum Number of Vowels in a Substring of Given Length

Medium Sliding Window Two Pointers

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<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        
        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;
    }
}