Taro Logo

Maximum Number of Vowels in a Substring of Given Length

Medium
Wayfair logo
Wayfair
1 view
Topics:
StringsSliding WindowsTwo Pointers

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum possible length of the input string `s` and what is the expected range for the integer `k`?
  2. Can the input string `s` be empty, or can `k` be zero or larger than the length of `s`? If so, what should I return?
  3. Is the input string `s` guaranteed to contain only lowercase English letters, or might it contain other characters?
  4. If there are multiple substrings with the same maximum number of vowels, do I need to return all of them, or just the count of vowels in one of them?
  5. Are we concerned about integer overflow if `k` is very large?

Brute Force Solution

Approach

The brute force method finds the maximum number of vowels by checking every possible short section of the word and counting the vowels in each. Think of it as sliding a window along the word, looking at every possible piece of the right size. It then picks the window with the most vowels.

Here's how the algorithm would work step-by-step:

  1. Start at the beginning of the word.
  2. Grab a piece of the word that is exactly the given length.
  3. Count how many vowels are in that piece.
  4. Remember that vowel count, if it's the highest one you've seen so far.
  5. Move the piece over by one letter.
  6. Grab the new piece of the word that is now under the 'window'.
  7. Count the vowels in this new piece.
  8. If this new count is higher than the highest you've seen, remember this new count instead.
  9. Keep repeating this process of sliding the piece, counting vowels, and updating the maximum count until you reach the end of the word where there aren't enough letters left to grab a piece of the required length.
  10. At the very end, the highest vowel count that you remembered is the answer.

Code Implementation

def max_vowels_brute_force(word, substring_length):
    maximum_number_of_vowels = 0

    # Iterate through all possible substrings
    for index in range(len(word) - substring_length + 1):
        substring = word[index:index + substring_length]
        number_of_vowels = 0

        # Count vowels in the substring
        for character in substring:
            if character in 'aeiou':
                number_of_vowels += 1

        # Update the maximum vowel count if needed
        if number_of_vowels > maximum_number_of_vowels:

            maximum_number_of_vowels = number_of_vowels

    return maximum_number_of_vowels

Big(O) Analysis

Time Complexity
O(n*k)The algorithm iterates through the string of length n, creating substrings of length k in each iteration. For each of these substrings, it counts the number of vowels by iterating through each character in the substring. Therefore, for each of the (n - k + 1) substrings, we perform k operations to count the vowels. Thus, the time complexity is O((n - k + 1) * k), which simplifies to O(n*k) when k is smaller than n. Note: k is considered to be the length of substring and n is length of the main string.
Space Complexity
O(1)The provided algorithm uses a fixed number of variables to keep track of the maximum vowel count seen so far. It doesn't create any additional data structures, like arrays or hash maps, whose size depends on the length of the input word. Therefore, the auxiliary space required remains constant regardless of the input size N (the length of the word) and is O(1).

Optimal Solution

Approach

The most efficient way to solve this is by focusing on the current window of letters. We'll slide this window across the entire string of letters, keeping track of the maximum number of vowels we've seen at any point.

Here's how the algorithm would work step-by-step:

  1. First, count the number of vowels in the initial substring of the specified length.
  2. Remember this initial count as the current maximum.
  3. Next, slide the substring one letter to the right. This means removing the leftmost letter and adding the next letter on the right.
  4. Update the vowel count by subtracting one if the removed letter was a vowel and adding one if the added letter is a vowel.
  5. Compare the new vowel count with the current maximum. If the new count is bigger, update the maximum.
  6. Repeat the sliding and counting steps until the substring reaches the end of the string of letters.
  7. The final maximum count is the answer.

Code Implementation

def find_max_vowels(input_string, substring_length):
    vowels = "aeiou"
    maximum_vowel_count = 0
    current_vowel_count = 0

    # Count vowels in the initial substring.
    for i in range(substring_length):
        if input_string[i] in vowels:
            current_vowel_count += 1

    maximum_vowel_count = current_vowel_count

    # Slide the window across the string.
    for i in range(substring_length, len(input_string)): 
        # Decrement if the leftmost character was a vowel.
        if input_string[i - substring_length] in vowels:
            current_vowel_count -= 1

        # Increment if the new character is a vowel.
        if input_string[i] in vowels:
            current_vowel_count += 1

        # Update the maximum vowel count if needed.
        if current_vowel_count > maximum_vowel_count:
            maximum_vowel_count = current_vowel_count

    return maximum_vowel_count

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the string once using a sliding window of a fixed size. In each iteration, a constant number of operations (addition, subtraction, and comparison) are performed to update the vowel count and maximum vowel count. Therefore, the time complexity is directly proportional to the length of the string, n, leading to a time complexity of O(n).
Space Complexity
O(1)The algorithm uses a fixed number of variables to store the current vowel count and the maximum vowel count encountered so far. These variables consume constant space regardless of the input string's length (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

CaseHow to Handle
Null or empty string inputReturn 0 immediately as there are no substrings to evaluate, preventing NullPointerException or incorrect calculations.
k is zero or negativeReturn 0 immediately because a substring of non-positive length is not valid.
k is greater than the length of the stringReturn 0 immediately because a substring longer than the string itself cannot exist.
String contains only consonantsThe sliding window approach will correctly count zero vowels for all windows, resulting in a final answer of 0.
String contains only vowelsThe sliding window approach will correctly count k vowels for the first window and the rest will be also k, resulting in a final answer of k.
k is equal to the length of the string and string contains both vowels and consonantsThe sliding window approach correctly counts all of the vowels to get the maximum.
Integer overflow if k is very largeNo risk of integer overflow in calculating vowel counts as they are bounded by the string length and k.
Large string inputThe sliding window approach provides an O(n) solution that scales linearly with the input string size.