{x}
blog image

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 Explanation: Maximum Number of Vowels in a Substring of Given Length

This problem asks to find the maximum number of vowels within any substring of length k in a given string s. The optimal approach is to use a sliding window technique.

Algorithm:

  1. Initialization:

    • Create a set vowels containing the vowel characters ('a', 'e', 'i', 'o', 'u').
    • Initialize a cnt variable to 0, representing the current count of vowels in the sliding window.
    • Initialize ans to 0, which will store the maximum number of vowels found.
    • Count the number of vowels in the first k characters of the string and assign this count to both cnt and ans.

  2. Sliding Window:

    • Iterate through the string starting from index k.
    • For each character:
      • Add 1 to cnt if the current character is a vowel.
      • Subtract 1 from cnt if the character at i - k (the character leaving the window) is a vowel.
      • Update ans to the maximum of ans and cnt.

  3. Return:

    • After iterating through the entire string, return ans.

Time Complexity: O(n), where n is the length of the string. The sliding window iterates through the string once.

Space Complexity: O(1). The space used is constant regardless of the input string size. The vowels set is of constant size.

Code Examples:

The solutions below demonstrate the sliding window approach in various programming languages. They all follow the same core logic. Differences mainly arise from syntax and built-in functions.

Python:

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")
        ans = cnt = sum(c in vowels for c in s[:k]) #Efficient vowel count in initial window
        for i in range(k, len(s)):
            cnt += (s[i] in vowels) - (s[i - k] in vowels) #increment/decrement based on vowel status
            ans = max(ans, cnt)
        return ans

Java:

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            if (vowels.contains(s.charAt(i))) {
                cnt++;
            }
        }
        int ans = cnt;
        for (int i = k; i < s.length(); i++) {
            if (vowels.contains(s.charAt(i))) {
                cnt++;
            }
            if (vowels.contains(s.charAt(i - k))) {
                cnt--;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (vowels.count(s[i])) cnt++;
        }
        int ans = cnt;
        for (int i = k; i < s.length(); ++i) {
            if (vowels.count(s[i])) cnt++;
            if (vowels.count(s[i - k])) cnt--;
            ans = max(ans, cnt);
        }
        return ans;
    }
};

JavaScript:

const maxVowels = (s, k) => {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    let cnt = 0;
    for (let i = 0; i < k; i++) {
        if (vowels.has(s[i])) cnt++;
    }
    let ans = cnt;
    for (let i = k; i < s.length; i++) {
        if (vowels.has(s[i])) cnt++;
        if (vowels.has(s[i - k])) cnt--;
        ans = Math.max(ans, cnt);
    }
    return ans;
};

These code examples provide a clear illustration of the sliding window technique for solving this problem efficiently. The choice of language depends on personal preference and project requirements.