2063. Vowels of All Substrings

MediumMathStringDynamic ProgrammingCombinatorics
Leetcode Link

Problem Description

The task is to calculate the total number of vowels present in all possible substrings of a given string, word. Vowels are the characters 'a', 'e', 'i', 'o', and 'u'. A substring is defined as any continuous sequence of characters within the string. It's important to note that since we are counting vowels in every possible substring, a single vowel can contribute to the count multiple times, depending on its position in the string and the number of substrings that include it. Also, the total count may be very large, so special attention should be paid to avoid integer overflow during the calculation.

Intuition

To find the solution without checking every possible substring directly, we can consider how many times each vowel contributes to the total count. A character at position i in the string word of length n is part of i + 1 substrings starting at or before position i and part of n - i substrings ending at or after position i. Therefore, that character is found in a total of (i + 1) * (n - i) substrings.

By looping through the characters of the word and checking if each character is a vowel, we can use the above formula to count how many times each vowel appears across all substrings. Then, summing these counts gives us the total number of vowels in all substrings. Python's list comprehension makes this process concise and efficient, as seen in the provided solution. This approach significantly reduces the computational complexity compared to the naive approach of generating and checking every possible substring individually.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution to this problem utilizes a single-pass algorithm along with the mathematical concept that each character in a string contributes to several substrings based on its position.

Here's a walk-through of the implementation steps with reference to the provided Python code:

  1. We determine the length n of the string word.
  2. We initialize a total sum of vowel occurrences in all substrings, which will be our final result. This sum starts at 0.
  3. We then iterate through the string word using a for loop with enumerate, which gives us each character c along with its index i.
  4. Within the loop, we check if the current character c is a vowel. This is accomplished by checking if c is in the string 'aeiou'.
  5. For every vowel found, we calculate its contribution to the total count. The number of times this vowel appears in all substrings is given by (i + 1) * (n - i), where i + 1 is the number of possible starting points for substrings that include this character, and n - i is the number of possible ending points.
  6. We add this contribution to the total sum for each vowel encountered.
  7. Finally, the total sum is returned as the result.

The provided solution uses a concise list comprehension that combines these steps into a single line. The sum function calculates the aggregate total by adding up the contributions from each vowel character in the string. Here's the core logic in the code:

1sum((i + 1) * (n - i) for i, c in enumerate(word) if c in 'aeiou')

This solution is efficient because it only involves processing each character of the string once and does not require generating all substrings explicitly. It has a time complexity of O(n), where n is the length of the string since it iterates through the string once, and each operation within the loop is constant time. There's no complex data structure used, and the space complexity is O(1) as it only keeps track of the total sum and loop variables.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's go through an example to illustrate the solution approach using the string word = "abcde".

  1. First, we determine the length of the string word, which is n = 5.

  2. We initialize the total sum of vowel occurrences in all substrings to 0. This will hold our result.

  3. Now, we iterate through the string word. For each iteration, we consider both the character c and its index i.

  4. Let's walk through each character of the string abcde:

    • For character a at index i = 0:

      1. We check if a is a vowel โ€” yes, it is.
      2. We calculate its contribution: (0 + 1) * (5 - 0) = 5.
      3. We add this to the total sum, so the sum is now 5.

    • For character b at index i = 1:

      1. b is not a vowel, so we do not count it.

    • For character c at index i = 2:

      1. c is also not a vowel, so we continue.

    • For character d at index i = 3:

      1. d is not a vowel, so we skip it as well.

    • For character e at index i = 4:

      1. We check if e is a vowel โ€” it is.
      2. We calculate its contribution: (4 + 1) * (5 - 4) = 5.
      3. We add this to the total sum, which becomes 5 (from a) + 5 (from e) = 10.

  5. Since there are no more characters in the string, we have completed our iteration. The total vowel occurrences in all possible substrings of "abcde" equal 10.

  6. We return 10 as the final result.

This walkthrough demonstrates the core logic of the provided Python code:

1sum((i + 1) * (5 - i) for i, c in enumerate("abcde") if c in 'aeiou')

By following these steps, we efficiently calculate the total number of vowel occurrences in all possible substrings of a given string.

Solution Implementation

1class Solution:
2    def count_vowels(self, word: str) -> int:
3        # Calculate the length of the word
4        word_length = len(word)
5
6        # Initialize a variable to hold the total count of vowels in all substrings
7        vowel_count = 0
8
9        # Iterate through each character in the word along with its index
10        for index, char in enumerate(word):
11            # Check if the current character is a vowel
12            if char in 'aeiou':
13                # If it's a vowel, calculate the contribution of this vowel to the total count
14                # The vowel contributes to all substrings that start before (or at) this character
15                # and end after (or at) this character. The number of such substrings can be calculated
16                # by multiplying the number of ways to choose a start point (index + 1 choices) by 
17                # the number of ways to choose an end point (word_length - index choices).
18                contribution = (index + 1) * (word_length - index)
19                # Add the contribution of this vowel to the total count
20                vowel_count += contribution
21
22        # Return the total count of vowels in all substrings
23        return vowel_count
24
1class Solution {
2    public long countVowels(String word) {
3        long totalCount = 0; // Initialize total count of vowels in substrings
4        int wordLength = word.length(); // Cache the length of the word for efficiency
5
6        // Iterate over each character in the word
7        for (int i = 0; i < wordLength; ++i) {
8            char currentChar = word.charAt(i); // Get the character at the current index
9
10            // Check if the current character is a vowel
11            if (currentChar == 'a' || currentChar == 'e' || currentChar == 'i' || currentChar == 'o' || currentChar == 'u') {
12                // If it's a vowel, add to the total count based on its position and remaining length
13                // The count is the product of the number of times this vowel can appear in
14                // the start of a substring (i+1 times) and in the end of a substring (wordLength - i times)
15                totalCount += (long) (i + 1) * (wordLength - i);
16            }
17        }
18      
19        // Return the total count of vowels found in all the substrings
20        return totalCount;
21    }
22}
23
1class Solution {
2public:
3    // Function to count the total number of vowel appearances in all substrings of the word.
4    long long countVowels(string word) {
5        long long totalVowels = 0; // Initialize a variable to keep track of the total vowels count.
6        int wordLength = word.size(); // Find the length of the word once to avoid multiple calls to `size()`.
7      
8        // Loop through each character of the word.
9        for (int i = 0; i < wordLength; ++i) {
10            char currentChar = word[i]; // Store the current character to compare it against vowels.
11          
12            // Check if the character is a vowel - 'a', 'e', 'i', 'o', or 'u'.
13            if (currentChar == 'a' || currentChar == 'e' || currentChar == 'i' || 
14                currentChar == 'o' || currentChar == 'u') {
15                // The number of times this vowel character will appear in all possible substrings
16                // is the product of its position (1-indexed) and its "rightward reach" (n - i).
17                totalVowels += (static_cast<long long>(i) + 1) * (wordLength - i);
18            }
19        }
20
21        // Return the total count of vowel appearances in all substrings.
22        return totalVowels;
23    }
24};
25
1// Function to count the total number of vowels in a given string, where each vowel
2// is counted as many times as it contributes to each possible substring.
3// @param {string} word - The word to count vowels in
4// @returns {number} - The total count of vowels contributing to substrings
5function countVowels(word: string): number {
6    const wordLength = word.length;
7    let vowelCount = 0;
8  
9    // Loop over all characters in the word
10    for (let index = 0; index < wordLength; ++index) {
11        // Check if the current character is a vowel
12        if (['a', 'e', 'i', 'o', 'u'].includes(word[index])) {
13            // If it is a vowel, add the count to the running total, factoring in
14            // the number of possible substrings it can be part of:
15            // Multiply the position of the vowel in the string (index + 1)
16            // by the number of ways to choose the ending of the substring (wordLength - index)
17            vowelCount += (index + 1) * (wordLength - index);
18        }
19    }
20  
21    // Return the total count of vowels
22    return vowelCount;
23}
24
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The given Python code snippet defines a function that counts the number of times a vowel appears in a string, such that each occurrence of a vowel is counted as many times as the number of substrings that include it.

Time Complexity: O(n)

The time complexity of the function is O(n) where n is the length of the input string word. This is because the function contains a single loop (created by the sum function and list comprehension) that iterates over each character in the string exactly once. Inside the loop, each step involves simple arithmetic operations that are constant time, namely (i + 1) * (n - i), and a membership test c in 'aeiou', which is also constant time since the set of vowels is of fixed size.

The calculation of the arithmetic progression is done for each vowel character in the string, thus the total operations scale linearly with the size of the input n.

Space Complexity: O(1)

The space complexity of the function is O(1). There are no data structures used that grow with the input size. Temporary variables like i and c are reused for each character in the string. The string 'aeiou' is a constant space that does not change with the input. Thus, the algorithm uses a fixed amount of space regardless of the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ