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

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'.

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 <= 105
• s consists of lowercase English letters.
• 1 <= k <= s.length

Solution:

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> set = new HashSet<>();

        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');

        int left = 0;
        int right = 0;
        int result = 0;
        int count = 0;
        while(right < s.length()){
            char cur = s.charAt(right);

            // update right

            if (set.contains(cur)){
                count++;
            }
            int curLen = right - left + 1;



            while (curLen > k && left < right){
                // move left
                char curLeft = s.charAt(left);
                if (set.contains(curLeft)){
                    count--;
                }    
                left++;
                curLen--;
            }
            if (curLen == k){
                result = Math.max(result, count);
            }

            right++;


        }

        return result;

    }
}

// "a b c i i i d e f", k = 3
//  l   r
// 

// TC: O(n)
// SC: O(n) // O(26) -> O(1)