Problem Statement

Given a string s and an integer k, return the highest number of vowels in any substring of s that is exactly k characters long. Vowels in English are 'a', 'e', 'i', 'o', and 'u'.

Examples

Example 1:

• Input: s = "azerdii", k = 4
• Expected Output: 2
• Justification: The substring "rdii" has two vowels ('i', 'i').

Example 2:

• Input: s = "abcde", k = 2
• Expected Output: 1
• Justification: The substring "ab" contains one vowel ('a').

Example 3:

• Input: s = "zaeixoyuxyz", k = 7
• Expected Output: 5
• Justification: The substring "aeixoyu" contains three vowels ('a', 'e', 'i', 'o', 'u').

Constraints:

• 1 <= s.length <= 10⁵
• s consists of lowercase English letters.
• 1 <= k <= s.length

Solution

To solve this problem, we will use a sliding window approach. This method allows us to efficiently keep track of the number of vowels in any substring of length k as we move through the string. We start by counting the vowels in the first k characters. Then, we slide the window one character to the right at a time, adjusting the vowel count by subtracting the character that is left behind and adding the new character that enters the window.

This approach is effective because it avoids recalculating the number of vowels from scratch for every substring, which would be inefficient. Instead, it updates the count in constant time, making the overall time complexity linear in relation to the length of the string.

Step-by-step Algorithm

1. Initialization:

   • Initialize two variables: maxVowels to keep track of the maximum number of vowels found in any window, and currentVowels to count the number of vowels in the current window.
   • Define a helper function isVowel(char ch) to check if a character is a vowel.

2. First Window Setup:

   • Iterate over the first k characters of the string s.
   • For each character in this range, check if it is a vowel using isVowel(). If it is, increment currentVowels.

3. Store Initial Count:

   • Set maxVowels to the value of currentVowels after processing the first k characters.

4. Sliding Window:

   • Iterate from the kth character to the end of the string.
   • For each character at position i:
     • Check if the character at position i is a vowel. If it is, increment currentVowels.
     • Check if the character at position i - k is a vowel. If it is, decrement currentVowels.
     • Update maxVowels to be the maximum of maxVowels and currentVowels.

5. Return Result:

   • Return the value of maxVowels.

Algorithm Walkthrough

Let's consider the input: s = "zaeixoyuxyz", k = 7

1. Initialization:

   • maxVowels = 0
   • currentVowels = 0
   • Define isVowel(char ch) to check if a character is 'a', 'e', 'i', 'o', or 'u'.

2. First Window Setup (characters: 'z', 'a', 'e', 'i', 'x', 'o', 'y'):

   • i = 0, s[0] = 'z' → Not a vowel, currentVowels = 0
   • i = 1, s[1] = 'a' → Vowel, currentVowels = 1
   • i = 2, s[2] = 'e' → Vowel, currentVowels = 2
   • i = 3, s[3] = 'i' → Vowel, currentVowels = 3
   • i = 4, s[4] = 'x' → Not a vowel, currentVowels = 3
   • i = 5, s[5] = 'o' → Vowel, currentVowels = 4
   • i = 6, s[6] = 'y' → Not a vowel, currentVowels = 4

3. Store Initial Count:

   • maxVowels = 4

4. Sliding Window:

   • i = 7, s[7] = 'u' → Vowel, currentVowels = 5

     • s[7-7] = s[0] = 'z' → Not a vowel, currentVowels = 5
     • maxVowels = max(4, 5) = 5

   • i = 8, s[8] = 'x' → Not a vowel, currentVowels = 5

     • s[8-7] = s[1] = 'a' → Vowel, currentVowels = 4
     • maxVowels = max(5, 4) = 5

   • i = 9, s[9] = 'y' → Not a vowel, currentVowels = 4

     • s[9-7] = s[2] = 'e' → Vowel, currentVowels = 3
     • maxVowels = max(5, 3) = 5

   • i = 10, s[10] = 'z' → Not a vowel, currentVowels = 3

     • s[10-7] = s[3] = 'i' → Vowel, currentVowels = 2
     • maxVowels = max(5, 2) = 5

5. Return Result:

   • Return maxVowels = 5