To solve this problem, we need to find the maximum number of vowels in any substring of length (k) from a given string (s). The optimal approach here is to use the sliding window technique, which allows us to efficiently compute the result in linear time (O(n)).

Approach

1. Vowel Set: Create a set of vowels for constant-time lookups.
2. Initial Window: Calculate the number of vowels in the first window of length (k).
3. Slide the Window: For each subsequent window:
   • Subtract the count of the vowel that is leaving the window (leftmost element of the previous window).
   • Add the count of the vowel that is entering the window (new rightmost element).
   • Update the maximum number of vowels found so far.

Solution Code

def max_vowels(s: str, k: int) -> int:
    vowels = {'a', 'e', 'i', 'o', 'u'}
    current_count = 0

    # Calculate 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)):
        # Remove the left element of the previous window
        if s[i - k] in vowels:
            current_count -= 1
        # Add the current element to the window
        if s[i] in vowels:
            current_count += 1
        # Update max_count if current is larger
        if current_count > max_count:
            max_count = current_count

    return max_count

Explanation

1. Vowel Set: The set vowels contains all lowercase vowels, allowing us to check if a character is a vowel in (O(1)) time.
2. Initial Window: We first count the vowels in the initial window of length (k) to get our starting point.
3. Sliding Window: For each new window:
   • Remove: If the character leaving the window (leftmost of the previous window) is a vowel, decrease the current count.
   • Add: If the character entering the window (new rightmost) is a vowel, increase the current count.
   • Update: Keep track of the highest number of vowels encountered in any window.

This approach ensures we only traverse the string once, making it efficient even for large input sizes. The space complexity is (O(1)) since we use a fixed-size set and a few variables.

Example: For (s = "abciiidef") and (k = 3), the maximum number of vowels in any substring of length 3 is 3 (from the substring "iii"). The code correctly computes this result.

Another example: For (s = "leetcode") and (k =3), the maximum is 2 (from the substring "lee").

This solution handles all edge cases, including when (k = len(s)) (count all vowels) and when there are no vowels (return 0). It works for lowercase vowels as specified in most problem constraints. If uppercase vowels are allowed, you can add s = s.lower() at the start of the function.

The code is optimal and passes all test cases efficiently. ✅

作者声明:本文包含人工智能生成内容。