Vowels of All Substrings

Vowels of All Substrings

What is this problem about?

The Vowels of All Substrings interview question asks you to calculate the total sum of vowels present in every possible substring of a given word. For example, if the word is "aba", the substrings are "a", "b", "a", "ab", "ba", and "aba". You would count the vowels in each and sum them up. The challenge lies in doing this efficiently, as a naive approach of generating all substrings would result in an O(n^2) or O(n^3) complexity, which is too slow for large inputs.

Why is this asked in interviews?

ServiceNow and other tech firms ask this to test a candidate's grasp of Combinatorics and Dynamic Programming. It's a classic example of moving from a "brute-force" mindset to a "contribution" mindset. Instead of asking "how many vowels are in this substring?", you ask "how many substrings is this specific vowel a part of?". This shift in perspective is a hallmark of an experienced software engineer.

Algorithmic pattern used

The core pattern here is Combinatorics and String interview pattern. For a character at index i in a string of length n, it can be the end of i + 1 possible starting positions (from index 0 to i) and the start of n - i possible ending positions (from index i to n-1). Therefore, the character at index i appears in exactly (i + 1) * (n - i) substrings. If that character is a vowel, you simply add this product to your total sum.

Example explanation

Consider the string "abc" with length n=3.

• Index 0: 'a' (vowel). It is in (0+1) * (3-0) = 3 substrings: {"a", "ab", "abc"}.
• Index 1: 'b' (consonant). We don't add its contribution to the vowel count.
• Index 2: 'c' (consonant). We don't add its contribution. Total vowel count = 3. If the string was "aba":
• 'a' at index 0 contributes 3.
• 'a' at index 2 contributes (2+1) * (3-2) = 3. Total = 6.

Common mistakes candidates make

The most common mistake is attempting to use a nested loop to iterate over all substrings. While this works for very short strings, it fails performance tests for strings with 10^5 characters. Another mistake is forgetting to use 64-bit integers (like long in Java or C++) for the total sum, as the result can easily exceed the capacity of a standard 32-bit integer.

Interview preparation tip

Practice "contribution to sum" problems. These appear frequently in competitive programming and high-level interviews. When you need to sum a property across all subarrays or substrings, always check if you can calculate how many times each element contributes to the final answer independently.