We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Vowels of All Substrings

Number: 2187

Difficulty: Medium

Paid? No

Companies: ServiceNow

Problem Description

Given a string word, count the total number of vowels (a, e, i, o, u) in every non-empty contiguous substring of word. Because the number of substrings can be enormous, an efficient solution is required rather than generating each substring explicitly.

Key Insights

  • Each letter in the string contributes to multiple substrings.
  • For a character at position i (0-indexed) in a string of length n:
    • It appears in (i + 1) substrings as the end element.
    • It appears in (n - i) substrings as the start element.
    • Therefore, the total number of substrings that include the character is (i + 1) * (n - i).
  • Thus, if the character is a vowel, you add (i + 1) * (n - i) to the total count.

Space and Time Complexity

Time Complexity: O(n) — A single pass over the string. Space Complexity: O(1) — Only a fixed number of extra variables are used.

Solution

The solution leverages the fact that each character participates in multiple substrings. For each vowel in the string, its total contribution is computed as (i + 1) multiplied by (n - i), where i is the character's index and n is the string's length. This avoids the need to generate all substrings and allows the computation to efficiently sum up the total vowel count.

The approach uses a simple loop and constant extra space, ensuring that even large inputs (up to 10^5 characters) are handled efficiently.

Code Solutions

# Python solution with line-by-line comments

def count_vowels(word):
    # Initialize total count to 0
    total = 0
    # Get the length of the input string
    n = len(word)
    # Define a set of vowels for quick lookup
    vowels = set("aeiou")
    
    # Iterate over each character and its index in the string
    for i, char in enumerate(word):
        # Check if the character is a vowel
        if char in vowels:
            # Each vowel contributes (i+1) * (n-i) to the total
            total += (i + 1) * (n - i)
    
    # Return the total count of vowels in all substrings
    return total

# Example usage:
print(count_vowels("aba"))
← Back to All Questions