Jobs

Interviews

Discussions

Count of Substrings Containing Every Vowel and K Consonants II

Medium

Bloomberg LP

0 views

Topics:

StringsTwo PointersSliding Windows

You are given a string word and a non-negative integer k.

Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

Example 1:

Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

Input: word = "aeiou", k = 0

Output: 1

Explanation:

The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".

Example 3:

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

word[0..5], which is "ieaouq".
word[6..11], which is "qieaou".
word[7..12], which is "ieaouq".

Constraints:

5 <= word.length <= 2 * 10⁵
word consists only of lowercase English letters.
0 <= k <= word.length - 5

Count of Substrings Containing Every Vowel and K Consonants II

Medium

Bloomberg LP

0 views

Topics:

StringsTwo PointersSliding Windows

You are given a string word and a non-negative integer k.

Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

Example 1:

Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

Input: word = "aeiou", k = 0

Output: 1

Explanation:

The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".

Example 3:

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

word[0..5], which is "ieaouq".
word[6..11], which is "qieaou".
word[7..12], which is "ieaouq".

Constraints:

5 <= word.length <= 2 * 10⁵
word consists only of lowercase English letters.
0 <= k <= word.length - 5

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string, and what characters can it contain besides lowercase English letters?
Can the value of 'K' be zero, negative, or larger than the number of consonants in the input string?
If no substring contains all vowels and K consonants, what should the function return?
Are we considering only contiguous substrings, or can the vowels and consonants be non-contiguous within the substring?
Is the order of vowels and consonants within the substring important, or are we only concerned with their presence and count?

Brute Force Solution

Approach

The brute force strategy involves checking every single possible substring of the given string. For each substring, we determine if it meets the criteria of containing all vowels and a specific number of consonants, counting the ones that do.

Here's how the algorithm would work step-by-step:

Look at the first character of the string.
Consider the substring starting with the first character and ending with the first character, then the substring starting with the first character and ending with the second character, then the substring starting with the first character and ending with the third character, and so on, until you reach the end of the string.
For each of these substrings, check if it has all the vowels and the required number of consonants.
If it does, increase the counter.
Now, move to the second character of the original string and repeat the same process of creating substrings, now starting at the second character.
Keep doing this, moving one character at a time, until you reach the last character of the original string.
Once you've considered all possible substrings, the counter will hold the total number of substrings that have all vowels and the specified number of consonants.

Code Implementation

def count_substrings(input_string, required_consonants):
    string_length = len(input_string)
    substring_count = 0

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            current_substring = input_string[start_index : end_index + 1]
            vowel_count = 0
            consonant_count = 0

            vowels = "aeiou"

            #Check if all vowels and required consonants
            for char in current_substring:
                if char in vowels:
                    vowel_count += 1
                elif 'a' <= char <= 'z':
                    consonant_count += 1

            # Check if the substring contains all vowels
            all_vowels_present = all(vowel in current_substring for vowel in vowels)

            #Check the vowel and consonant requirements
            if all_vowels_present and consonant_count == required_consonants:
                substring_count += 1

    return substring_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible substrings of the input string of length n. Generating these substrings requires a nested loop structure, where the outer loop iterates from the start of the string to the end, and the inner loop expands the substring to the right. For each substring, the algorithm checks if it contains all vowels and the required number of consonants, which involves iterating through the substring again. Thus, the time complexity is O(n * n * n), or O(n³).

Space Complexity

O(1) – The provided algorithm checks every substring for vowel and consonant counts. It does not explicitly use any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited substrings. Only a few integer variables are needed to store the count of vowels, consonants, and potentially loop indices. Therefore, the auxiliary space used is constant and independent of the input string's length N.

Optimal Solution

Approach

The most efficient way to solve this problem involves a focused search through the string, rather than checking every single substring. We use a 'sliding window' approach combined with tracking to determine valid substrings more quickly. This way, we don't have to check every substring from scratch.

Here's how the algorithm would work step-by-step:

First, we need a way to quickly tell if a substring has all the vowels. We'll create a system to remember which vowels we've seen as we look at the string.
We also need to count how many consonants we've seen. We'll keep a separate count for the consonants.
Now, we start from the beginning of the string and expand a 'window' to the right, one character at a time.
As we expand the window, we update our vowel tracker and consonant count.
Once the window contains all the vowels and has at least the required number of consonants, we know we have a valid substring.
Instead of immediately starting a new window, we try to shrink the window from the left. This is the 'sliding' part. We keep shrinking the window as long as we still have all the vowels and the required number of consonants.
For every position where the window is valid (all vowels and enough consonants), we increase our total count of valid substrings.
After shrinking the window as much as possible, we move the entire window one position to the right and repeat the process of expanding and shrinking.
We continue this process until we reach the end of the string. The final count is the total number of substrings that contain all the vowels and the required number of consonants.

Code Implementation

def count_substrings(input_string, required_consonants):
    string_length = len(input_string)
    vowels = "aeiou"
    total_substring_count = 0

    for left in range(string_length):
        vowel_presence = {'a': False, 'e': False, 'i': False, 'o': False, 'u': False}
        consonant_count = 0
        for right in range(left, string_length):
            character = input_string[right]
            if character in vowels:
                vowel_presence[character] = True
            else:
                consonant_count += 1

            all_vowels_present = all(vowel_presence.values())

            # Check if the substring is valid.
            if all_vowels_present and consonant_count >= required_consonants:

                # Shrink the window from the left.
                temp_left = left
                while temp_left <= right:
                    temp_character = input_string[temp_left]
                    temp_vowel_presence = vowel_presence.copy()
                    temp_consonant_count = consonant_count

                    if temp_character in vowels:
                        temp_vowel_presence[temp_character] = False
                        if not all(temp_vowel_presence.values()):
                            total_substring_count += (string_length - right)
                            break
                    else:
                        temp_consonant_count -= 1
                        if temp_consonant_count < required_consonants:
                            total_substring_count += (string_length - right)
                            break

                    total_substring_count += (string_length - right)
                    temp_left += 1

                break

    return total_substring_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n using a sliding window approach. The outer loop expands the window from left to right. The inner loop, which shrinks the window, only runs when the current window satisfies the criteria (all vowels and K consonants). In the worst case, each character is visited a constant number of times (at most twice, once by the expanding window and at most once by the shrinking window). Therefore, the overall time complexity is proportional to the length of the string, resulting in O(n).

Space Complexity

O(1) – The solution uses a vowel tracker (to remember which vowels are present) and a consonant count. The vowel tracker can be implemented using a fixed-size data structure, like an array or a bitmask of size 5 (since there are 5 vowels), thus taking constant space. The consonant count is a single integer variable, also requiring constant space. Therefore, the auxiliary space used by the algorithm does not depend on the input string's length (N) and remains constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0, as no substrings can be formed from an empty string.
String length less than 5 (number of vowels)	Return 0, because a substring needs at least one of each vowel.
String contains only vowels (k > 0 is impossible)	If k > 0, return 0, as no consonants exist.
String contains no vowels	Return 0, because no substring can contain all vowels.
k = 0 and string contains all vowels at least once	Count all substrings, as any substring containing all vowels satisfies the condition.
Large input string causing potential integer overflow in count	Use 64-bit integer type (long in Java, long long in C++) for counting substrings.
Input string contains non-alphabetic characters	Ignore non-alphabetic characters or throw an exception, depending on requirements.
Maximum input string length, leading to performance issues with naive O(n^2) solution	Optimize using sliding window or other more efficient algorithms with O(n) time complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string, and what characters can it contain besides lowercase English letters?
Can the value of 'K' be zero, negative, or larger than the number of consonants in the input string?
If no substring contains all vowels and K consonants, what should the function return?
Are we considering only contiguous substrings, or can the vowels and consonants be non-contiguous within the substring?
Is the order of vowels and consonants within the substring important, or are we only concerned with their presence and count?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the first character of the string.
Consider the substring starting with the first character and ending with the first character, then the substring starting with the first character and ending with the second character, then the substring starting with the first character and ending with the third character, and so on, until you reach the end of the string.
For each of these substrings, check if it has all the vowels and the required number of consonants.
If it does, increase the counter.
Now, move to the second character of the original string and repeat the same process of creating substrings, now starting at the second character.
Keep doing this, moving one character at a time, until you reach the last character of the original string.
Once you've considered all possible substrings, the counter will hold the total number of substrings that have all vowels and the specified number of consonants.

Code Implementation

def count_substrings(input_string, required_consonants):
    string_length = len(input_string)
    substring_count = 0

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            current_substring = input_string[start_index : end_index + 1]
            vowel_count = 0
            consonant_count = 0

            vowels = "aeiou"

            #Check if all vowels and required consonants
            for char in current_substring:
                if char in vowels:
                    vowel_count += 1
                elif 'a' <= char <= 'z':
                    consonant_count += 1

            # Check if the substring contains all vowels
            all_vowels_present = all(vowel in current_substring for vowel in vowels)

            #Check the vowel and consonant requirements
            if all_vowels_present and consonant_count == required_consonants:
                substring_count += 1

    return substring_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need a way to quickly tell if a substring has all the vowels. We'll create a system to remember which vowels we've seen as we look at the string.
We also need to count how many consonants we've seen. We'll keep a separate count for the consonants.
Now, we start from the beginning of the string and expand a 'window' to the right, one character at a time.
As we expand the window, we update our vowel tracker and consonant count.
Once the window contains all the vowels and has at least the required number of consonants, we know we have a valid substring.
Instead of immediately starting a new window, we try to shrink the window from the left. This is the 'sliding' part. We keep shrinking the window as long as we still have all the vowels and the required number of consonants.
For every position where the window is valid (all vowels and enough consonants), we increase our total count of valid substrings.
After shrinking the window as much as possible, we move the entire window one position to the right and repeat the process of expanding and shrinking.
We continue this process until we reach the end of the string. The final count is the total number of substrings that contain all the vowels and the required number of consonants.

Code Implementation

def count_substrings(input_string, required_consonants):
    string_length = len(input_string)
    vowels = "aeiou"
    total_substring_count = 0

    for left in range(string_length):
        vowel_presence = {'a': False, 'e': False, 'i': False, 'o': False, 'u': False}
        consonant_count = 0
        for right in range(left, string_length):
            character = input_string[right]
            if character in vowels:
                vowel_presence[character] = True
            else:
                consonant_count += 1

            all_vowels_present = all(vowel_presence.values())

            # Check if the substring is valid.
            if all_vowels_present and consonant_count >= required_consonants:

                # Shrink the window from the left.
                temp_left = left
                while temp_left <= right:
                    temp_character = input_string[temp_left]
                    temp_vowel_presence = vowel_presence.copy()
                    temp_consonant_count = consonant_count

                    if temp_character in vowels:
                        temp_vowel_presence[temp_character] = False
                        if not all(temp_vowel_presence.values()):
                            total_substring_count += (string_length - right)
                            break
                    else:
                        temp_consonant_count -= 1
                        if temp_consonant_count < required_consonants:
                            total_substring_count += (string_length - right)
                            break

                    total_substring_count += (string_length - right)
                    temp_left += 1

                break

    return total_substring_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0, as no substrings can be formed from an empty string.
String length less than 5 (number of vowels)	Return 0, because a substring needs at least one of each vowel.
String contains only vowels (k > 0 is impossible)	If k > 0, return 0, as no consonants exist.
String contains no vowels	Return 0, because no substring can contain all vowels.
k = 0 and string contains all vowels at least once	Count all substrings, as any substring containing all vowels satisfies the condition.
Large input string causing potential integer overflow in count	Use 64-bit integer type (long in Java, long long in C++) for counting substrings.
Input string contains non-alphabetic characters	Ignore non-alphabetic characters or throw an exception, depending on requirements.
Maximum input string length, leading to performance issues with naive O(n^2) solution	Optimize using sliding window or other more efficient algorithms with O(n) time complexity.