Problem Description

You are given a string word. Your task is to find the total count of vowels across all possible substrings of this string.

A substring is any contiguous sequence of characters from the string. For example, if word = "abc", the substrings are: "a", "b", "c", "ab", "bc", and "abc".

The vowels are the characters 'a', 'e', 'i', 'o', and 'u'.

For each substring, count how many vowels it contains, then sum up all these counts to get the final answer.

Example breakdown: If word = "aba":

• Substring "a" (position 0): contains 1 vowel
• Substring "b" (position 1): contains 0 vowels
• Substring "a" (position 2): contains 1 vowel
• Substring "ab" (positions 0-1): contains 1 vowel
• Substring "ba" (positions 1-2): contains 1 vowel
• Substring "aba" (positions 0-2): contains 2 vowels
• Total: 1 + 0 + 1 + 1 + 1 + 2 = 6

The solution uses a mathematical approach: for each vowel at position i, it appears in exactly (i + 1) × (n - i) substrings, where n is the length of the string. This is because:

• There are (i + 1) ways to choose the starting position of a substring that includes position i (any position from 0 to i)
• There are (n - i) ways to choose the ending position (any position from i to n-1)

Note: The result can be very large and may exceed the range of a 32-bit signed integer, so use appropriate data types to handle large numbers.

Intuition

The naive approach would be to generate all possible substrings and count vowels in each one. However, this would be inefficient with time complexity of O(n³) - we'd need O(n²) to generate all substrings and O(n) to count vowels in each.

Instead of counting how many vowels are in each substring, let's flip our perspective: for each vowel in the string, count how many substrings contain it. This is the key insight that leads to an efficient solution.

Consider a vowel at position i in the string. In how many substrings does this vowel appear?

To include the character at position i in a substring, we need to:

1. Choose a starting position for the substring that is at or before position i
2. Choose an ending position that is at or after position i

For the starting position, we can choose any index from 0 to i (inclusive), giving us (i + 1) choices.

For the ending position, we can choose any index from i to n - 1 (inclusive), giving us (n - i) choices.

Since these choices are independent, the total number of substrings containing the character at position i is (i + 1) × (n - i).

For example, if we have string "abcde" (length 5) and want to count substrings containing the character at index 2:

• Starting positions: 0, 1, or 2 → 3 choices or (2 + 1)
• Ending positions: 2, 3, or 4 → 3 choices or (5 - 2)
• Total substrings: 3 × 3 = 9

By calculating this contribution for each vowel and summing them up, we get the total count of vowels across all substrings in just O(n) time.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Solution Approach

The implementation follows directly from our intuition about counting each vowel's contribution to all substrings.

We iterate through each character in the string along with its index using enumerate(word). For each character at position i:

1. Check if it's a vowel: We use the condition c in 'aeiou' to determine if the current character is a vowel.

2. Calculate its contribution: If the character is a vowel, we calculate how many substrings contain it using the formula (i + 1) * (n - i), where:

   • i + 1 represents the number of possible starting positions (from index 0 to i)
   • n - i represents the number of possible ending positions (from index i to n-1)
   • n is the total length of the string

3. Sum all contributions: We use Python's sum() function with a generator expression to accumulate the contributions of all vowels in a single pass.

The entire solution is elegantly expressed in one line:

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

Time Complexity: O(n) where n is the length of the string. We make a single pass through the string.

Space Complexity: O(1) as we only use a constant amount of extra space for variables. The generator expression doesn't create an intermediate list but calculates values on-the-fly.

Example walkthrough with word = "aba":

• n = 3
• Index 0, character 'a': vowel → contribution = (0 + 1) * (3 - 0) = 1 * 3 = 3
• Index 1, character 'b': not a vowel → contribution = 0
• Index 2, character 'a': vowel → contribution = (2 + 1) * (3 - 2) = 3 * 1 = 3
• Total = 3 + 0 + 3 = 6

Example Walkthrough

Looking at the solution approach, let me create a clear walkthrough with a small example.

Let's use word = "code" to illustrate the solution approach.

Step 1: Identify the vowels and their positions

• Index 0: 'c' - not a vowel
• Index 1: 'o' - vowel ✓
• Index 2: 'd' - not a vowel
• Index 3: 'e' - vowel ✓

Step 2: Calculate each vowel's contribution

For the vowel 'o' at index 1:

• Number of possible starting positions: i + 1 = 1 + 1 = 2 (can start at index 0 or 1)
• Number of possible ending positions: n - i = 4 - 1 = 3 (can end at index 1, 2, or 3)
• Contribution: 2 × 3 = 6
• These 6 substrings are: "o", "co", "od", "cod", "ode", "code"

For the vowel 'e' at index 3:

• Number of possible starting positions: i + 1 = 3 + 1 = 4 (can start at index 0, 1, 2, or 3)
• Number of possible ending positions: n - i = 4 - 3 = 1 (can only end at index 3)
• Contribution: 4 × 1 = 4
• These 4 substrings are: "e", "de", "ode", "code"

Step 3: Sum all contributions

• Total = 6 (from 'o') + 4 (from 'e') = 10

Verification (optional check): Let's verify by listing all substrings and their vowel counts:

• "c" → 0, "o" → 1, "d" → 0, "e" → 1
• "co" → 1, "od" → 1, "de" → 1
• "cod" → 1, "ode" → 2
• "code" → 2
• Sum: 0+1+0+1+1+1+1+1+2+2 = 10 ✓

The formula (i + 1) × (n - i) efficiently counts how many substrings include each vowel position without explicitly generating all substrings.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. The algorithm iterates through each character in the string exactly once using enumerate(), and for each character, it performs constant-time operations: checking if the character is a vowel (membership test in a fixed-size string 'aeiou' is O(1)), and if so, performing arithmetic operations (i + 1) * (n - i) which are also O(1). The sum() function processes the generator expression in linear time.

The space complexity is O(1). The algorithm uses only a constant amount of extra space regardless of the input size. The variables used are:

• The generator expression doesn't create a list but yields values one at a time
• The loop variables i and c use constant space
• The accumulator in sum() uses constant space
• The string 'aeiou' for vowel checking is a constant-size literal

The generator expression ensures that no additional data structure proportional to the input size is created, maintaining constant space usage.

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

Common Pitfalls

1. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, the result can overflow a 32-bit integer. For example, with a string of length 100,000 containing all vowels, the result would be approximately 10^15, which exceeds the range of a 32-bit integer.

Solution: Use a 64-bit integer type (long in Java, long long in C++):

# Python handles this automatically, but in other languages:
# Java: use long instead of int
# C++: use long long instead of int

2. Brute Force Approach - Generating All Substrings

A common mistake is actually generating all substrings and counting vowels in each, leading to O(n²) or O(n³) complexity:

# INEFFICIENT approach - Don't do this!
def countVowels_inefficient(word):
    total = 0
    n = len(word)
    for i in range(n):
        for j in range(i, n):
            substring = word[i:j+1]  # O(n) operation
            for char in substring:    # Another O(n) loop
                if char in 'aeiou':
                    total += 1
    return total

Solution: Use the mathematical formula that counts each vowel's contribution directly without generating substrings.

3. Incorrect Formula Application

Mixing up the formula components or using wrong indices:

# INCORRECT formulas:
# Wrong: (i) * (n - i - 1)  # Missing +1 on left side
# Wrong: (i + 1) * (n - i + 1)  # Extra +1 on right side
# Wrong: (n - i) * (i + 1)  # Same result but less intuitive ordering

Solution: Remember the formula as: (starting_positions) × (ending_positions) = (i + 1) × (n - i)

4. Case Sensitivity Issues

Forgetting to handle uppercase vowels if the problem requires it:

# If the string might contain uppercase letters:
def countVowels_case_insensitive(word):
    n = len(word)
    return sum(
        (i + 1) * (n - i)
        for i, c in enumerate(word)
        if c.lower() in 'aeiou'  # Convert to lowercase before checking
    )

Solution: Always clarify whether the input is guaranteed to be lowercase or if you need to handle both cases.

5. Off-by-One Errors in Manual Implementation

When implementing without enumerate, forgetting that indices are 0-based:

# Error-prone manual indexing:
def countVowels_manual(word):
    n = len(word)
    total = 0
    for i in range(n):  # Correct: range(n) gives 0 to n-1
        if word[i] in 'aeiou':
            # Easy to mess up: is it i or i+1? n-i or n-i-1?
            total += (i + 1) * (n - i)
    return total

Solution: Use enumerate() for cleaner, more readable code, or carefully verify your index calculations with small examples.