We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Vowels in a Substring of Given Length

Number: 1567

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Apple

Problem Description

Given a string s and an integer k, return the maximum number of vowels in any substring of s with length k. The vowels considered are 'a', 'e', 'i', 'o', and 'u'.

Key Insights

  • Use the sliding window technique to efficiently evaluate substrings of length k.
  • Maintain a running count of vowels within the current window.
  • When sliding the window, subtract the count if the exiting character is a vowel and add if the new incoming character is a vowel.
  • The approach is efficient with a time complexity of O(n).

Space and Time Complexity

Time Complexity: O(n), where n is the length of string s. Space Complexity: O(1), since only constant extra space is used.

Solution

We solve the problem by implementing a sliding window. First, count the vowels in the initial window of size k. Then continue sliding the window one character at a time. For each slide, if the character that exits is a vowel, decrement the count; if the entering character is a vowel, increment the count. Track the maximum count during this process. This method ensures each character is processed once for an efficient solution.

Code Solutions

# Python solution using sliding window algorithm

def maxVowels(s: str, k: int) -> int:
    vowels = set("aeiou")  # Set for quick vowel lookup
    current_count = 0

    # Count vowels in the initial window of size k
    for i in range(k):
        if s[i] in vowels:
            current_count += 1
    max_count = current_count  # Initialize max_count with the count of the first window

    # Slide the window through the string
    for i in range(k, len(s)):
        if s[i - k] in vowels:  # Remove letter going out of the window
            current_count -= 1
        if s[i] in vowels:  # Add incoming letter
            current_count += 1
        max_count = max(max_count, current_count)  # Update maximum found so far

    return max_count

# Example usage:
# print(maxVowels("abciiidef", 3))
← Back to All Questions