Vowels of All Substrings

Medium

Asked by:

18 views

Topics:

Strings

Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.

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

Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

Example 1:

Input: word = "aba"
Output: 6
Explanation: 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.

Example 2:

Input: word = "abc"
Output: 3
Explanation: 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

Example 3:

Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".

Constraints:

1 <= word.length <= 10⁵
word consists of lowercase English letters.

Try coding it in LeetCode

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'?
Can the input string 'word' be empty or null?
Is the input string guaranteed to contain only lowercase English letters, or should I handle other characters?
Could you provide a clarifying example of the expected output for a small input string?
Are we concerned with integer overflow in the calculation of the total count of vowels?

Brute Force Solution

Approach

The brute force method tackles this vowel counting problem by looking at every possible piece of the given string. It checks each piece, no matter how small or large, to see if it contains vowels. Finally, it adds up the vowel counts from all those pieces.

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

First, consider all single letters in the string. Check each letter to see if it's a vowel.
Next, consider all pairs of letters next to each other. Check each pair to see if it contains any vowels.
Then, consider all groups of three letters next to each other. Check each group for vowels.
Continue this process, looking at groups of four letters, five letters, and so on, up to the entire string.
For each group of letters you consider, count how many vowels it contains.
Finally, add up all the vowel counts from all the groups of letters you considered. This total is the answer.

Code Implementation

def vowels_of_all_substrings_brute_force(input_string):
    string_length = len(input_string)
    total_vowel_count = 0

    for substring_length in range(1, string_length + 1):
        for starting_index in range(string_length - substring_length + 1):
            substring = input_string[starting_index:starting_index + substring_length]
            vowel_count_in_substring = 0

            # Iterate through each char in the substring to count vowels
            for char in substring:
                if char in 'aeiouAEIOU':
                    vowel_count_in_substring += 1

            # Accumulate vowel counts across all substrings
            total_vowel_count += vowel_count_in_substring

    return total_vowel_count

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible substrings of the given string of length n. The outer loop considers substrings of length 1 to n. The inner loop iterates through all possible starting positions for each substring length. For each substring, it iterates through each character to check if it's a vowel. Thus, we have nested loops resulting in O(n * n * n) operations, which simplifies to O(n³).

Space Complexity

O(1) – The brute force method, as described, iterates through substrings of the input string but doesn't explicitly create any auxiliary data structures that scale with the input size N (length of the string). While it considers substrings, it only needs constant space to store temporary variables for iteration or vowel counts within each substring. Therefore, the space complexity remains constant, independent of the input string's length.

Optimal Solution

Approach

The straightforward way is slow, checking every possible substring. Instead, this approach focuses on how many substrings each vowel is part of. This clever trick allows us to quickly count vowels in all substrings without actually looking at each substring individually.

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

Think about each character in the word, one at a time.
For each character, figure out how many substrings include that character.
If the character is a vowel, the number of substrings it's part of is based on its position. Multiply the position of the vowel and the number of remaining characters to the right of that vowel, including the vowel itself.
Add these numbers together across all vowels in the word. This final number is the total count of vowels present in all possible substrings of the word.

Code Implementation

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

    for index in range(word_length):
        character = word[index]

        # Only process if the character is a vowel
        if character in 'aeiou':

            # Calculate substrings the vowel is part of
            substrings_with_vowel = (index + 1) * (word_length - index)

            # Add to total vowel substrings count
            total_vowel_substrings += substrings_with_vowel

    return total_vowel_substrings

Big(O) Analysis

Time Complexity

O(n) – The provided approach iterates through the string once, examining each character. For each character, it performs a constant-time calculation to determine the number of substrings the vowel contributes to. Therefore, the time complexity is directly proportional to the length of the input string, n, making it O(n).

Space Complexity

O(1) – The algorithm iterates through the input string and calculates the number of substrings each vowel contributes to, but it doesn't store substrings or intermediate results in auxiliary data structures. It only uses a few integer variables to keep track of the current character position and the running total of vowel occurrences across all substrings. Therefore, the auxiliary space required is constant, independent of the input string's length (N).

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there are no substrings and therefore no vowels.
String with a single character that is not a vowel	Return 0, as the single substring does not contain a vowel.
String with a single character that is a vowel	Return 1, as the single substring contains one vowel.
String with all vowels	The solution must correctly count all vowel occurrences in all substrings.
String with no vowels	The solution should return 0 as no substring will contain vowels.
Very long input string (scalability)	Ensure the solution uses an algorithm with acceptable time complexity (e.g., O(n) or O(n log n) to avoid timeouts).
String contains only one type of vowel (e.g., 'aaaa')	The solution should correctly handle the multiple occurrences of same vowel.
Integer overflow in count of substrings and vowels when the length of string is very large	Use a data type that can hold large numbers (e.g., long in Java or C++, or appropriate integer type in Python).

Null or empty input string

How to Handle:

Return 0 immediately as there are no substrings and therefore no vowels.

String with a single character that is not a vowel

How to Handle:

Return 0, as the single substring does not contain a vowel.

String with a single character that is a vowel

How to Handle:

Return 1, as the single substring contains one vowel.

String with all vowels

How to Handle:

The solution must correctly count all vowel occurrences in all substrings.

String with no vowels

How to Handle:

The solution should return 0 as no substring will contain vowels.

Very long input string (scalability)

How to Handle:

Ensure the solution uses an algorithm with acceptable time complexity (e.g., O(n) or O(n log n) to avoid timeouts).

String contains only one type of vowel (e.g., 'aaaa')

How to Handle:

The solution should correctly handle the multiple occurrences of same vowel.

Integer overflow in count of substrings and vowels when the length of string is very large

How to Handle:

Use a data type that can hold large numbers (e.g., long in Java or C++, or appropriate integer type in Python).