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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Vowels in a Substring of Given Length

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires finding the maximum count of vowels in any substring of a fixed length k.
  • A sliding window approach is efficient for this problem as it allows us to evaluate each substring of length k without re-evaluating the entire substring for each position.
  • We can maintain a count of vowels as we slide the window across the string.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string s.
Space Complexity: O(1) as we are using a fixed amount of space for counting vowels.

Solution

We will use a sliding window approach to maintain a window of size k as we traverse the string. We will count the number of vowels in the current window, and update the maximum count found as we move the window one character at a time.

  1. Initialize a count of vowels in the first window of size k.
  2. Slide the window by removing the leftmost character and adding the next character in the string.
  3. Update the vowel count accordingly and track the maximum count encountered.

Code Solutions

def maxVowels(s: str, k: int) -> int:
    vowels = set('aeiou')  # Set of vowel characters
    max_count = 0
    current_count = 0
    
    # Count vowels in the first window
    for i in range(k):
        if s[i] in vowels:
            current_count += 1
    max_count = current_count
    
    # Slide the window across the string
    for i in range(k, len(s)):
        if s[i] in vowels:
            current_count += 1  # Add new character
        if s[i - k] in vowels:
            current_count -= 1  # Remove old character
        max_count = max(max_count, current_count)  # Update max count
    
    return max_count
← Back to All Questions