Jobs

Interviews

Discussions

Count Vowel Substrings of a String

Easy

Bloomberg LP

0 views

Topics:

StringsTwo PointersSliding Windows

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

Constraints:

1 <= word.length <= 100
word consists of lowercase English letters only.

Count Vowel Substrings of a String

Easy

Bloomberg LP

0 views

Topics:

StringsTwo PointersSliding Windows

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

Constraints:

1 <= word.length <= 100
word consists of lowercase English letters only.

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 `word`?
Is the input string guaranteed to contain only lowercase English letters, or might there be other characters present?
If the string `word` does not contain all five vowels, should I return 0?
Could the input string `word` be empty or null?
Are we concerned about the length of the vowel substrings containing all five vowels, or just the count?

Brute Force Solution

Approach

The brute force approach means we're going to look at every possible group of letters inside the given word. We'll check each group to see if it has only vowels and if it contains all the vowels at least once.

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

Consider the first letter and every letter after it, one at a time, creating a substring.
Then, move to the second letter and do the same, creating more substrings that start later in the word.
Repeat this process, moving down the word until you've created every possible substring.
For each substring you created, check if it contains only the vowels a, e, i, o, and u.
If the substring has only vowels, check if it has at least one of each vowel.
If a substring contains only vowels and has at least one of each vowel, then count it.
Finally, after checking every substring, report the total number of valid vowel substrings.

Code Implementation

def count_vowel_substrings_brute_force(word):
    number_of_vowel_substrings = 0
    word_length = len(word)

    for start_index in range(word_length):
        for end_index in range(start_index, word_length):
            substring = word[start_index:end_index + 1]

            # Verify only vowels are in the current substring
            if all(char in 'aeiou' for char in substring):

                vowels_present = set()

                for char in substring:
                    vowels_present.add(char)

                # Check if all vowels are present in substring
                if len(vowels_present) == 5:
                    number_of_vowel_substrings += 1

    return number_of_vowel_substrings

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible substrings of the input string of length n. Generating all substrings takes O(n²) time because for each starting position, we iterate to the end of the string. For each substring, it checks if the substring contains only vowels, which takes O(n) time in the worst case (checking each character). Therefore, the overall time complexity is O(n² * n), which simplifies to O(n³).

Space Complexity

O(1) – The described brute force approach iterates through all possible substrings and checks each one for vowel properties. The checks for vowel content and presence of all vowels are performed using a fixed number of variables to track the counts or existence of each vowel. There are no auxiliary data structures like arrays, hashmaps, or sets allocated whose size depends on the input string's length, denoted as N. Therefore, the space used is constant and independent of the input size.

Optimal Solution

Approach

The best way to count vowel substrings is to avoid checking every possible substring. Instead, we cleverly check each possible starting position and extend the substring only as long as it contains all the required vowels, stopping early when the conditions are not met.

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

Go through each position in the string, one by one, considering it as a potential start of a vowel substring.
For each starting position, build a substring by adding one character at a time from the original string.
As you build the substring, keep track of which vowels ('a', 'e', 'i', 'o', 'u') are present in the substring.
If the substring contains all five vowels, increase the count of vowel substrings.
If you encounter a non-vowel character while building the substring, stop building from that starting position and move to the next starting position. You know that any further extension will not be a valid vowel substring.
Continue this process for all starting positions to efficiently count all vowel substrings.

Code Implementation

def count_vowel_substrings(word):
    substring_count = 0
    word_length = len(word)

    for start_index in range(word_length):
        vowel_counts = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
        
        for end_index in range(start_index, word_length):
            current_character = word[end_index]
            
            if current_character in 'aeiou':
                vowel_counts[current_character] += 1
                
                # Check if all vowels are present in the substring.
                if all(vowel_counts[vowel] > 0 for vowel in 'aeiou'):
                    substring_count += 1
            else:
                # Stop if a non-vowel is encountered
                break

    return substring_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n characters of the input string as a potential starting position for a vowel substring. For each starting position, it extends the substring until either all five vowels are found or a non-vowel character is encountered. In the worst-case scenario, the substring extends close to n characters from each starting position, leading to a nested loop-like behavior. Therefore, the total number of operations is approximately n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm keeps track of which vowels are present in the current substring. This can be done using a fixed-size data structure, like a boolean array of size 5 (one element for each vowel), or a bitmask. The size of this data structure is independent of the input string's length, N. No other data structures that scale with N are used. Therefore, the auxiliary space is constant.

Edge Cases

Case	How to Handle
Empty input string	Return 0 immediately as there are no substrings.
String with length less than 5	Return 0, as at least 5 characters are needed to potentially contain all five vowels.
String contains non-vowel characters	Ignore substrings containing non-vowels as they cannot be vowel substrings; only consider contiguous sequences of vowels.
String with only one vowel type repeated	Return 0 as it's impossible to have all five vowels if only one vowel exists.
String where no substring contains all five vowels	The solution should correctly iterate and return 0 if no valid substring is found.
String with very long length	Ensure the algorithm has reasonable time complexity (e.g., O(n^2) or better) to avoid timeouts.
String containing all vowels but not contiguously	Only count contiguous substrings, not arrangements of vowels separated by consonants.
String with multiple occurrences of all five vowels	The solution should count all valid substrings, even if they overlap or are contained within each other.

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 `word`?
Is the input string guaranteed to contain only lowercase English letters, or might there be other characters present?
If the string `word` does not contain all five vowels, should I return 0?
Could the input string `word` be empty or null?
Are we concerned about the length of the vowel substrings containing all five vowels, or just the count?

Brute Force Solution

Approach

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

Consider the first letter and every letter after it, one at a time, creating a substring.
Then, move to the second letter and do the same, creating more substrings that start later in the word.
Repeat this process, moving down the word until you've created every possible substring.
For each substring you created, check if it contains only the vowels a, e, i, o, and u.
If the substring has only vowels, check if it has at least one of each vowel.
If a substring contains only vowels and has at least one of each vowel, then count it.
Finally, after checking every substring, report the total number of valid vowel substrings.

Code Implementation

def count_vowel_substrings_brute_force(word):
    number_of_vowel_substrings = 0
    word_length = len(word)

    for start_index in range(word_length):
        for end_index in range(start_index, word_length):
            substring = word[start_index:end_index + 1]

            # Verify only vowels are in the current substring
            if all(char in 'aeiou' for char in substring):

                vowels_present = set()

                for char in substring:
                    vowels_present.add(char)

                # Check if all vowels are present in substring
                if len(vowels_present) == 5:
                    number_of_vowel_substrings += 1

    return number_of_vowel_substrings

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through each position in the string, one by one, considering it as a potential start of a vowel substring.
For each starting position, build a substring by adding one character at a time from the original string.
As you build the substring, keep track of which vowels ('a', 'e', 'i', 'o', 'u') are present in the substring.
If the substring contains all five vowels, increase the count of vowel substrings.
If you encounter a non-vowel character while building the substring, stop building from that starting position and move to the next starting position. You know that any further extension will not be a valid vowel substring.
Continue this process for all starting positions to efficiently count all vowel substrings.

Code Implementation

def count_vowel_substrings(word):
    substring_count = 0
    word_length = len(word)

    for start_index in range(word_length):
        vowel_counts = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
        
        for end_index in range(start_index, word_length):
            current_character = word[end_index]
            
            if current_character in 'aeiou':
                vowel_counts[current_character] += 1
                
                # Check if all vowels are present in the substring.
                if all(vowel_counts[vowel] > 0 for vowel in 'aeiou'):
                    substring_count += 1
            else:
                # Stop if a non-vowel is encountered
                break

    return substring_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return 0 immediately as there are no substrings.
String with length less than 5	Return 0, as at least 5 characters are needed to potentially contain all five vowels.
String contains non-vowel characters	Ignore substrings containing non-vowels as they cannot be vowel substrings; only consider contiguous sequences of vowels.
String with only one vowel type repeated	Return 0 as it's impossible to have all five vowels if only one vowel exists.
String where no substring contains all five vowels	The solution should correctly iterate and return 0 if no valid substring is found.
String with very long length	Ensure the algorithm has reasonable time complexity (e.g., O(n^2) or better) to avoid timeouts.
String containing all vowels but not contiguously	Only count contiguous substrings, not arrangements of vowels separated by consonants.
String with multiple occurrences of all five vowels	The solution should count all valid substrings, even if they overlap or are contained within each other.