Vowels of All Substrings

Medium
1231.

Vowels of All Substrings

Vowels of All Substrings is a medium coding problem on strings, dynamic programming and math, asked in Amazon and Google interviews.

Given a string word, consider every one of its non-empty substrings (contiguous runs of characters). For each substring count its vowels ('a', 'e', 'i', 'o' and 'u'), and return the sum of those counts over all substrings.

Substrings at different positions are counted separately even if they read the same.

The length bound below is tightened from the original problem so that the answer always fits in a 32-bit signed integer.

Example 1

Input
word = "kairo"
Output
22
Explanation
The `a` at index 1 lies in 2 × 4 = 8 substrings, the `i` at index 2 in 3 × 3 = 9 and the `o` at index 4 in 5 × 1 = 5.

Example 2

Input
word = "ae"
Output
4
Explanation
`"a"`, `"e"` and `"ae"` hold 1, 1 and 2 vowels.

Example 3

Input
word = "xyz"
Output
0

Constraints

  • 1 <= word.length <= 2000
  • word consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var countVowels = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Vowels of All Substrings — Solution in Python, Java & C++

Vowels of All Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Vowels of All Substrings is a medium coding problem on strings, dynamic programming and math, asked in Amazon and Google interviews.

Problem statement

Given a string word, consider every one of its non-empty substrings (contiguous runs of characters). For each substring count its vowels ('a', 'e', 'i', 'o' and 'u'), and return the sum of those counts over all substrings.

Substrings at different positions are counted separately even if they read the same.

The length bound below is tightened from the original problem so that the answer always fits in a 32-bit signed integer.

Example 1

Input: word = "kairo"
Output: 22
Explanation: The `a` at index 1 lies in 2 × 4 = 8 substrings, the `i` at index 2 in 3 × 3 = 9 and the `o` at index 4 in 5 × 1 = 5.

Example 2

Input: word = "ae"
Output: 4
Explanation: `"a"`, `"e"` and `"ae"` hold 1, 1 and 2 vowels.

Example 3

Input: word = "xyz"
Output: 0

Constraints

  • 1 <= word.length <= 2000
  • word consists of lowercase English letters

Hints for Vowels of All Substrings

  1. Hint 1

    Instead of looking at each substring, flip it around: how many substrings contain a given position?

  2. Hint 2

    A substring containing index i starts somewhere in 0..i and ends somewhere in i..n-1.

  3. Hint 3

    So the vowel at index i is counted (i + 1) × (n - i) times. Sum that over the vowels.

How to solve Vowels of All Substrings

Count by contribution: the character at index i belongs to exactly (i + 1) × (n - i) substrings, so each vowel adds that many to the total.

Approach

  1. Let n be the length of word.
  2. For each index i holding a vowel, add (i + 1) × (n - i) to the answer.
  3. Return the sum (computed in 64-bit arithmetic where the language needs it).

Why it works

The requested sum counts pairs (substring, vowel position inside it). Grouping those pairs by the vowel instead of by the substring gives the same total. A substring word[l..r] contains i exactly when 0 <= l <= i and i <= r <= n - 1, which is (i + 1) choices for l times (n - i) choices for r.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Enumerating substrings is O(n²) or worse; the contribution formula is linear.
  • In the original problem n reaches 10^5 and the sum needs 64 bits; here n <= 2000 keeps it below 2^31, but accumulate in a wide type anyway.
  • y is not a vowel here.

Reference solution

Python

def countVowels(word: str) -> int:
    n = len(word)
    total = 0
    for i, ch in enumerate(word):
        if ch in "aeiou":
            total += (i + 1) * (n - i)
    return total

Java

public static int countVowels(String word) {
    int n = word.length();
    long total = 0;
    for (int i = 0; i < n; i++) {
        if ("aeiou".indexOf(word.charAt(i)) >= 0) total += (long) (i + 1) * (n - i);
    }
    return (int) total;
}

C++

int countVowels(string word) {
    long long n = word.size(), total = 0;
    for (long long i = 0; i < n; i++) {
        char c = word[i];
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') total += (i + 1) * (n - i);
    }
    return (int)total;
}

JavaScript

var countVowels = function(word) {
    var n = word.length, total = 0;
    for (var i = 0; i < n; i++) {
        if ("aeiou".indexOf(word[i]) >= 0) total += (i + 1) * (n - i);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming