Problem

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

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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

1
2
3

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

Constraints

  • 1 <= word.length <= 10^5
  • word consists of lowercase English letters.

Solution

Method 1 – Combinatorial Counting

Intuition

Each vowel at position i appears in all substrings that start at or before i and end at or after i. The number of such substrings is (i+1) * (n-i) for a string of length n.

Approach

Iterate through the string. For each vowel at index i, add (i+1)*(n-i) to the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    long long countVowels(string word) {
        long long ans = 0, n = word.size();
        for (int i = 0; i < n; ++i) {
            char c = word[i];
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                ans += (long long)(i + 1) * (n - i);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func countVowels(word string) int64 {
    n := int64(len(word))
    ans := int64(0)
    for i, c := range word {
        if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
            ans += int64(i+1) * (n - int64(i))
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public long countVowels(String word) {
        long ans = 0, n = word.length();
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                ans += (long)(i + 1) * (n - i);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun countVowels(word: String): Long {
        var ans = 0L
        val n = word.length
        for (i in word.indices) {
            val c = word[i]
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                ans += (i + 1).toLong() * (n - i)
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def countVowels(self, word: str) -> int:
        n = len(word)
        vowels = set('aeiou')
        ans = 0
        for i, c in enumerate(word):
            if c in vowels:
                ans += (i + 1) * (n - i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

pub fn count_vowels(word: &str) -> i64 {
    let n = word.len() as i64;
    let mut ans = 0i64;
    for (i, c) in word.chars().enumerate() {
        if matches!(c, 'a' | 'e' | 'i' | 'o' | 'u') {
            ans += (i as i64 + 1) * (n - i as i64);
        }
    }
    ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function countVowels(word: string): number {
    const n = word.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const c = word[i];
        if ('aeiou'.includes(c)) {
            ans += (i + 1) * (n - i);
        }
    }
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n) — One pass through the string.
  • 🧺 Space complexity: O(1) — Only a few variables are used.