Leetcode 1456: Maximum Number of Vowels in a Substring of Given Length

Input: The input consists of a string `s` and an integer `k`.

Example: Input: s = "programming", k = 4

Constraints:

• 1 <= s.length <= 100,000

• s consists of only lowercase English letters.

• 1 <= k <= s.length

Output: Return the maximum number of vowels in any substring of `s` with length `k`.

Example: Output: 2

Constraints:

• The output must be a single integer representing the maximum count of vowels.

• If there are multiple substrings with the same maximum count, return the count as a single value.

Goal: Determine the maximum number of vowels present in any substring of length `k`.

Steps:

• Define a helper function to identify vowels efficiently.

• Use a sliding window approach to count vowels in substrings of length `k`.

• Adjust the count dynamically as the window moves forward in the string.

• Track and update the maximum count of vowels encountered.

Goal: The conditions that input values must satisfy.

Steps:

• `s` is a non-empty string with only lowercase English letters.

• `k` is a positive integer and less than or equal to the length of `s`.

Assumptions:

• The input string and integer are valid and meet the constraints.

• Substrings of length `k` are always possible as `k <= s.length`.

• Input: Input: s = "basketball", k = 5

• Explanation: Output: 2. The substring "asket" contains 2 vowels ('a' and 'e').

• Input: Input: s = "university", k = 3

• Explanation: Output: 2. Substring "uni" contains 2 vowels ('u' and 'i').

• Input: Input: s = "robot", k = 4

• Explanation: Output: 1. The substring "obot" contains 1 vowel ('o').

Approach: Utilize a sliding window approach to efficiently count vowels in each substring of length `k`.

Observations:

• Vowels are a small, fixed subset of characters, so membership checks can be done using a set.

• Sliding window helps avoid recomputing the vowel count for overlapping substrings.

• Efficient implementation requires linear time complexity.

• Use a sliding window to maintain a running count of vowels as we traverse the string.

Steps:

• Initialize a set for vowels {'a', 'e', 'i', 'o', 'u'}.

• Start with the first `k` characters of the string and count the vowels.

• Move the window by one character at a time, adding the next character's contribution and removing the previous one.

• Update the maximum count whenever a higher count is observed.

• Return the maximum count after processing all substrings.

Empty Inputs:

• Not applicable as `s` is guaranteed to have at least one character.

Large Inputs:

• Input: s with length 100,000 and k close to s.length. Verify performance.

Special Values:

• Input: s = "aaaaa", k = 3 -> Output: 3. Handles case with all vowels.

• Input: s = "bcdfg", k = 2 -> Output: 0. Handles case with no vowels.

Constraints:

• Ensure the function handles edge cases like `k = 1` or `k = s.length` gracefully.

int vowels[26] = {  1,0,0,0,1, 0,0,0,1,0, 
                    0,0,0,0,1, 0,0,0,0,0, 
                    1,0,0,0,0, 0 };
int maxVowels(string s, int k) {
    int mx = 0;
    for(int i = 0, cur = 0; i < s.size(); i++) {
        cur += vowels[s[i] - 'a'];
        if(i >= k) cur -= vowels[s[i-k] - 'a'];
        mx = max(cur, mx);
    }
    return mx;
}

1 : Array Initialization

int vowels[26] = {  1,0,0,0,1, 0,0,0,1,0,

This array 'vowels' is used to mark the presence of vowels in the alphabet. Each element corresponds to a letter, where vowels are marked with a '1' and consonants with a '0'.

2 : Array Initialization

                    0,0,0,0,1, 0,0,0,0,0,

Continues the initialization of the 'vowels' array. This ensures that the vowels (a, e, i, o, u) are marked with '1' while other letters are marked with '0'.

3 : Array Initialization

                    1,0,0,0,0, 0 };

Finalizes the 'vowels' array initialization, ensuring that all vowels are marked as '1'.

4 : Function Declaration

int maxVowels(string s, int k) {

The function 'maxVowels' is declared. It takes a string 's' and an integer 'k', and returns an integer representing the maximum number of vowels in any substring of length 'k'.

5 : Variable Initialization

    int mx = 0;

The variable 'mx' is initialized to zero, which will later hold the maximum number of vowels encountered in any substring of length 'k'.

6 : Loop

    for(int i = 0, cur = 0; i < s.size(); i++) {

A loop starts, iterating through each character in the string 's'. The variable 'cur' keeps track of the current count of vowels in the current sliding window of length 'k'.

7 : Vowel Count Update

        cur += vowels[s[i] - 'a'];

The 'cur' variable is updated by adding 1 if the current character 's[i]' is a vowel (as determined by the 'vowels' array).

8 : Sliding Window Adjustment

        if(i >= k) cur -= vowels[s[i-k] - 'a'];

If the index 'i' is greater than or equal to 'k', the character that is sliding out of the window (at position 'i-k') is subtracted from 'cur'.

9 : Max Vowel Update

        mx = max(cur, mx);

The variable 'mx' is updated to store the maximum value between 'cur' (the current count of vowels in the window) and the previous maximum count.

10 : Return Statement

    return mx;

The function returns the value of 'mx', which is the maximum number of vowels found in any substring of length 'k'.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The sliding window traverses the string once, making it linear in terms of `n`, the length of the string.

Best Case: O(1)

Worst Case: O(1)

Description: Only a fixed amount of space is used for tracking the count and vowel set.

Leetcode 1456: Maximum Number of Vowels in a Substring of Given Length

Explore →