Leetcode 2063: Vowels of All Substrings

Input: You are given the following input:

Example: Input: word = "abcabc"

Constraints:

• 1 <= word.length <= 10^5

• word consists of lowercase English letters.

Output: The output should be a single integer representing the sum of vowels in every substring of the given string word.

Example: Output: 9

Constraints:

• The result may be a large integer.

Goal: The goal is to calculate the sum of vowels in all substrings of the string word efficiently, considering that the string may be very large.

Steps:

• 1. Iterate through each character of the string.

• 2. For each vowel encountered, calculate how many substrings it is part of.

• 3. Add the contribution of each vowel to the total sum.

• 4. Return the result.

Goal: The input string can be large, so an efficient approach is necessary.

Steps:

• The solution should work within the given time limits for strings with length up to 10^5.

Assumptions:

• The word consists of lowercase English letters.

• The length of the word is at least 1.

• Input: Input: word = "aba"

• Explanation: The possible substrings are: 'a', 'ab', 'aba', 'b', 'ba', 'a'. The vowels are found in substrings 'a', 'ab', 'ba', 'a', 'aba', and contribute 6 vowels in total.

• Input: Input: word = "abc"

• Explanation: The possible substrings are: 'a', 'ab', 'abc', 'b', 'bc', and 'c'. Only 'a', 'ab', and 'abc' contain vowels, contributing 3 vowels in total.

• Input: Input: word = "ltcd"

• Explanation: There are no vowels in the string 'ltcd', so the total sum of vowels is 0.

Approach: The problem can be solved efficiently by calculating the contribution of each vowel to all substrings it appears in. The key observation is that a vowel at position i contributes to all substrings starting from indices 0 to i and ending from i to the end of the string.

Observations:

• Each vowel appears in multiple substrings, and the number of such substrings can be calculated directly.

• A brute force approach of generating all substrings would be too slow for large strings.

• The efficient approach avoids generating substrings and directly computes the contribution of each vowel in the string.

Steps:

• Step 1: Initialize a variable to track the total number of vowels.

• Step 2: Iterate through each character of the string.

• Step 3: For each vowel, calculate how many substrings it is part of and add its contribution to the total.

• Step 4: Return the total sum of vowels.

Empty Inputs:

• There are no empty inputs since the length of the string is guaranteed to be at least 1.

Large Inputs:

• For large inputs (strings up to length 10^5), ensure the algorithm runs in linear time.

Special Values:

• If the word contains no vowels, the result should be 0.

Constraints:

• Ensure the solution handles edge cases such as very short or very long strings efficiently.

long long countVowels(string word) {
    long long res = 0, n = word.size();
    for(int i = 0; i < n; i++)
    if(string("aeiou").find(word[i]) != string::npos)
    res += (i + 1) * (n - i);
    return res;
}

1 : Variable Initialization

long long countVowels(string word) {

Define the function 'countVowels' which takes a string 'word' as input and returns the total count of substrings containing vowels.

2 : Variable Initialization

    long long res = 0, n = word.size();

Initialize 'res' to 0, which will hold the result, and 'n' to the length of the input string 'word'.

3 : Looping

    for(int i = 0; i < n; i++)

Start a loop that iterates over each character in the string 'word'.

4 : Conditional Logic

    if(string("aeiou").find(word[i]) != string::npos)

Check if the current character 'word[i]' is a vowel by looking for it in the string 'aeiou'. If found, the character is a vowel.

5 : Mathematical Operation

    res += (i + 1) * (n - i);

If the character is a vowel, add to 'res' the product of the number of possible substrings starting with the current vowel position.

6 : Return Statement

    return res;

Return the accumulated result 'res' which contains the total count of substrings with vowels.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the word, because we only need to iterate through the string once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as the solution only requires a constant amount of extra space.

Leetcode 2063: Vowels of All Substrings

Explore →