Grokking 75: Top Coding Interview Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Maximum Number of Vowels in a Substring of Given Length
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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<sup>5</sup>
  • 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
Image

Code

Python3
Python3

. . . .

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. This is because we scan the string once to initialize the first window and then slide the window across the string.
  • Space Complexity: O(1). We use a constant amount of extra space regardless of the size of the input.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible