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


Problem Description

The problem asks for the maximum number of vowel letters that can be found in any substring of a given string s with a fixed length k. The vowels in English are defined as 'a', 'e', 'i', 'o', and 'u'. A substring is any continuous sequence of characters in the string. For example, if s is "banana" and k is 3, we need to find the substring of length 3 that has the most vowels. This problem is solved by checking each possible substring of length k and finding the one with the most vowels.

Intuition

To solve this problem efficiently, we use a technique called the sliding window algorithm. The idea is to maintain a window of size k that slides over the string s from the beginning to the end. This window keeps track of the number of vowels in the current substring of length k.

Here are the steps to implement this approach:

  1. Initialize a set of vowels for quick look-up.
  2. Start by counting the number of vowels in the first substring of length k.
  3. As you slide the window by one position to the right, add one to the count if the incoming character is a vowel and subtract one if the outgoing character is a vowel.
  4. Update the maximum number of vowels found so far.

This way, you don't have to check each substring from scratch; you just update the count based on the characters that are entering and exiting the window as it slides. This makes the solution very efficient because each character in s is processed exactly once.

Solution Approach

The implementation uses the sliding window technique alongside a set for fast vowel checking, and simple arithmetic operations for counting. Let's break down the steps and logic used in the solution:

  1. Create a Set of Vowels: First, a set containing the vowels 'aeiou' is created for O(1) lookup times. This is done to quickly determine if a character is a vowel.

    1vowels = set('aeiou')
  2. Count Vowels in the First Window: Next, the number of vowels in the first window (the first k characters) of the string is counted. This forms our initial maximum.

    1t = sum(c in vowels for c in s[:k])
    2ans = t
  3. Slide the Window: The algorithm then iterates through the string starting from the kth character. For each new character that enters the window, we add 1 to t if it's a vowel. Simultaneously, we subtract 1 from t if the character that is exiting the window (which is i - k characters behind the current character) is a vowel.

    1for i in range(k, len(s)):
    2    t += s[i] in vowels
    3    t -= s[i - k] in vowels
  4. Update Maximum: After adjusting the count for the new window position, we check if the current count t is greater than our recorded maximum ans. If it is, we update ans to be equal to t.

    1ans = max(ans, t)
  5. Return Result: After sliding through the entire string, ans will hold the maximum number of vowels found in any substring of length k. This result is then returned.

    1return ans

The simplicity and efficiency of this solution come from the fact that each character is looked at exactly twice per iteration (once when it enters the window and once when it leaves), leading to an O(n) runtime complexity where n is the length of the string s.

Example Walkthrough

Let's illustrate the solution approach using the string s = "celebration" and k = 5. We are looking for the maximum number of vowels in any substring of length 5.

  1. Create a Set of Vowels: We initialize a set containing the vowels for quick look-up.

    1vowels = set('aeiou')
  2. Count Vowels in the First Window: Our first window is 'celeb'. We count the number of vowels in this window.

    1t = sum(c in vowels for c in "celeb")  # t = 2 ('e' and 'e')
    2ans = t  # ans = 2
  3. Slide the Window: Now we start sliding the window one character at a time to the right and adjust the count t.

    • Move 1: New window is 'elebr'. We add 1 for 'e' (new) and do not subtract any because 'c' (old) is not a vowel.

      t now becomes 3 (from 'e', 'e', 'a'), and ans remains 3 because 3 > 2.

    • Move 2: New window is 'lebra'. We add 1 for 'a' (new) and subtract 1 for 'e' (old).

      t remains 3 (from 'e', 'e', 'a'), and ans remains 3.

    • Move 3: New window is 'ebrat'. We add 1 for 'a' (new) and subtract 1 for 'e' (old).

      t remains 3 (from 'e', 'e', 'a'), and ans remains 3.

    • Move 4: New window is 'brati'. We add 1 for 'i' (new) and do not subtract any because 'l' (old) is not a vowel.

      t now becomes 3 (from 'e', 'a', 'i'), and ans remains 3.

    • Move 5: New window is 'ratio'. We add 1 for 'o' (new) and subtract 1 for 'b' (old).

      t now becomes 3 (from 'a', 'i', 'o'), and ans remains 3.

    • Move 6: New window 'ation'. We add 1 for 'a' (new) and subtract 1 for 'r' (old).

      t now becomes 3 (from 'a', 'i', 'o'), and ans remains 3.

    In each move, we adjust t and update ans if necessary:

    1for i in range(5, len(s)):
    2    t += s[i] in vowels
    3    t -= s[i - 5] in vowels
    4    ans = max(ans, t)
  4. Return Result: After sliding through the entire string s, we find that ans = 3 is the maximum number of vowels we can find in any substring of length 5.

The final result for this example is 3, which means the maximum number of vowels found in any substring of length 5 in the string "celebration" is three.

Python Solution

1class Solution:
2    def maxVowels(self, s: str, k: int) -> int:
3        # Define a set containing all vowels for easy access and checking
4        vowels = set('aeiou')
5
6        # Initial count of vowels in the first window of size k
7        current_vowel_count = sum(char in vowels for char in s[:k])
8
9        # Initialize maximum vowels found in a window
10        max_vowel_count = current_vowel_count
11
12        # Slide the window by one character from the kth element to the end
13        for i in range(k, len(s)):
14            # Increase count if the incoming character is a vowel
15            current_vowel_count += s[i] in vowels
16            # Decrease count since we are leaving the character at the start of the window
17            current_vowel_count -= s[i - k] in vowels
18
19            # Update maximum if the current window has more vowels than previous maximum
20            max_vowel_count = max(max_vowel_count, current_vowel_count)
21
22        # Return the maximum number of vowels found in any window of size k
23        return max_vowel_count
24

Java Solution

1class Solution {
2    /**
3     * Calculates the maximum number of vowels in any substring of length k.
4     *
5     * @param s The input string.
6     * @param k The length of the substring.
7     * @return The maximum number of vowels found in any substring of length k.
8     */
9    public int maxVowels(String s, int k) {
10        // Initialize the total vowel count for the first window of size k
11        int totalVowelsInWindow = 0, 
12            stringLength = s.length();
13
14        // Count the number of vowels in the initial window of size k
15        for (int i = 0; i < k; ++i) {
16            if (isVowel(s.charAt(i))) {
17                ++totalVowelsInWindow;
18            }
19        }
20
21        // Initialize the answer with the vowel count of the first window
22        int maxVowels = totalVowelsInWindow;
23
24        // Slide the window of size k across the string
25        for (int i = k; i < stringLength; ++i) {
26            // If the newly included character is a vowel, increase the count
27            if (isVowel(s.charAt(i))) {
28                ++totalVowelsInWindow;
29            }
30
31            // If the character that got excluded from the window is a vowel, decrease the count
32            if (isVowel(s.charAt(i - k))) {
33                --totalVowelsInWindow;
34            }
35
36            // Update maxVowels if the current window has more vowels than the previous ones
37            maxVowels = Math.max(maxVowels, totalVowelsInWindow);
38        }
39
40        // Return the maximum number of vowels found
41        return maxVowels;
42    }
43
44    /**
45     * Helper method to check if a character is a vowel.
46     *
47     * @param character The character to be checked.
48     * @return true if the character is a vowel, false otherwise.
49     */
50    private boolean isVowel(char character) {
51        // A character is a vowel if it is one of 'a', 'e', 'i', 'o', or 'u'
52        return character == 'a' || 
53               character == 'e' || 
54               character == 'i' || 
55               character == 'o' || 
56               character == 'u';
57    }
58}
59

C++ Solution

1class Solution {
2public:
3    // Function to find the maximum number of vowels in any substring of length k
4    int maxVowels(string s, int k) {
5        int count = 0; // Initialize counter for vowels
6        int maxVowelCount = 0; // This will store the maximum count of vowels found
7        int strLength = s.size(); // Store the length of the string
8
9        // Count the number of vowels in the first window of size k
10        for (int i = 0; i < k; ++i)
11            count += isVowel(s[i]); 
12      
13        maxVowelCount = count; // Initialize maximum vowel count to be the count from the first window
14
15        // Slide the window by one position to the right each time and update counts
16        for (int i = k; i < strLength; ++i) {
17            count += isVowel(s[i]); // Add a vowel count for new character in the window
18            count -= isVowel(s[i - k]); // Subtract a vowel count for the character that is no longer in the window
19            maxVowelCount = max(maxVowelCount, count); // Update maximum count if current window has more vowels
20        }
21
22        return maxVowelCount; // Return the maximum number of vowels found in any substring of length k
23    }
24
25    // Helper function to check if a character is a vowel
26    bool isVowel(char c) {
27        // A character is a vowel if it is 'a', 'e', 'i', 'o', or 'u'
28        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
29    }
30};
31

Typescript Solution

1// Define a function that checks if a character is a vowel
2function isVowel(char: string): boolean {
3    return ['a', 'e', 'i', 'o', 'u'].includes(char.toLowerCase());
4}
5
6// Define a function that finds the maximum number of vowels in a substring of length k within string s
7function maxVowels(s: string, k: number): number {
8    // Initialize total vowel count for the first window of size k
9    let totalVowels = 0;
10    for (let i = 0; i < k; ++i) {
11        if (isVowel(s[i])) {
12            totalVowels++;
13        }
14    }
15
16    // Store the maximum number of vowels found in a window of size k
17    let maxVowelCount = totalVowels;
18
19    // Use a sliding window to count vowels in the remaining windows of size k
20    for (let i = k; i < s.length; ++i) {
21        // Add a vowel count if the newly included character is a vowel
22        if (isVowel(s[i])) {
23            totalVowels++;
24        }
25        // Subtract a vowel count if the excluded character from the left of the window was a vowel
26        if (isVowel(s[i - k])) {
27            totalVowels--;
28        }
29        // Update maximum vowel count if the current window has more vowels
30        maxVowelCount = Math.max(maxVowelCount, totalVowels);
31    }
32
33    // Return the maximum number of vowels found in any window of size k
34    return maxVowelCount;
35}
36

Time and Space Complexity

Time Complexity

The provided code has a time complexity of O(n) where n is the length of the string s. This is because the code iterates over each character of the string exactly once beyond the initial window setup. The initial sum calculation for the first k characters is O(k), and each subsequent step in the loop is constant time O(1) because it involves adding or subtracting one and checking for the existence of a character in a set, which is also O(1). Since k is at most n, the entire operation is bounded by O(n).

Space Complexity

The space complexity of the code is O(1). The space used does not grow with the size of the input string s. The set of vowels is of constant size (containing 5 elements) and does not change. The variables t and ans use a constant amount of space and there are no data structures that grow with the size of the input.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫