Count Vowel Substrings of a String

Medium
1030.

Count Vowel Substrings of a String

Count Vowel Substrings of a String is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Cognizant interviews.

A vowel substring is a contiguous substring made up only of vowels (a, e, i, o, u) that contains all five of them at least once.

Return the number of vowel substrings of word.

Example 1

Input
word = "aeiouu"
Output
2
Explanation
`aeiou` and `aeiouu`.

Example 2

Input
word = "codekairo"
Output
0
Explanation
Consonants break every run, so no all-vowel substring exists.

Example 3

Input
word = "cuaieuouac"
Output
7

Constraints

  • 1 <= word.length <= 100
  • word consists of lowercase English letters only.
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 countVowelSubstrings = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Vowel Substrings of a String — Problem & Solution

Count Vowel Substrings of a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Vowel Substrings of a String is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Cognizant interviews.

Problem statement

A vowel substring is a contiguous substring made up only of vowels (a, e, i, o, u) that contains all five of them at least once.

Return the number of vowel substrings of word.

Example 1

Input: word = "aeiouu"
Output: 2
Explanation: `aeiou` and `aeiouu`.

Example 2

Input: word = "codekairo"
Output: 0
Explanation: Consonants break every run, so no all-vowel substring exists.

Example 3

Input: word = "cuaieuouac"
Output: 7

Constraints

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

Hints for Count Vowel Substrings of a String

  1. Hint 1

    A consonant ends every candidate — the substring must be entirely vowels.

  2. Hint 2

    For each starting index, extend right while the characters stay vowels and count once all five have appeared.

  3. Hint 3

    At n <= 100 the quadratic enumeration is comfortable.

How to solve Count Vowel Substrings of a String

For each start index, extend a window right while the characters remain vowels, tracking how many distinct vowels have been seen. Every extension after the fifth distinct vowel arrives is another valid substring.

Approach

  1. For each i, reset a set of seen vowels.
  2. Extend j from i; break out on a consonant.
  3. Count the substring whenever the set holds all five vowels.

Why it works

Breaking on a consonant is what keeps this near-linear in practice — the inner loop never crosses one, so the total work is the sum of the squares of the vowel-run lengths, not n². The sliding-window version tracks the smallest window covering all five and adds its left-extension count, which is O(n) but far harder to get exactly right.

Complexity

  • Time — O(n²) in the worst case, and much less when consonants are common
  • Space — O(1) — at most five distinct vowels

Pitfalls

  • The substring must contain no consonants, not merely start and end with vowels.
  • All five vowels are required — four is not enough.
  • Longer substrings that still qualify each count separately.

Reference solution

Python

def countVowelSubstrings(word: str) -> int:
    vowels = set("aeiou")
    count = 0
    for i in range(len(word)):
        seen = set()
        for j in range(i, len(word)):
            if word[j] not in vowels:
                break
            seen.add(word[j])
            if len(seen) == 5:
                count += 1
    return count

Java

public static int countVowelSubstrings(String word) {
    String V = "aeiou";
    int count = 0;
    for (int i = 0; i < word.length(); i++) {
        boolean[] seen = new boolean[5];
        int distinct = 0;
        for (int j = i; j < word.length(); j++) {
            int idx = V.indexOf(word.charAt(j));
            if (idx < 0) break;
            if (!seen[idx]) { seen[idx] = true; distinct++; }
            if (distinct == 5) count++;
        }
    }
    return count;
}

C++

int countVowelSubstrings(string word) {
    string V = "aeiou";
    int count = 0;
    for (int i = 0; i < (int) word.size(); i++) {
        bool seen[5] = {false, false, false, false, false};
        int distinct = 0;
        for (int j = i; j < (int) word.size(); j++) {
            size_t idx = V.find(word[j]);
            if (idx == string::npos) break;
            if (!seen[idx]) { seen[idx] = true; distinct++; }
            if (distinct == 5) count++;
        }
    }
    return count;
}

JavaScript

var countVowelSubstrings = function(word) {
    var V = "aeiou", count = 0;
    for (var i = 0; i < word.length; i++) {
        var seen = {}, distinct = 0;
        for (var j = i; j < word.length; j++) {
            var c = word.charAt(j);
            if (V.indexOf(c) === -1) break;
            if (!seen[c]) { seen[c] = true; distinct++; }
            if (distinct === 5) count++;
        }
    }
    return count;
};

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 · Hashing: Hash Maps and Hash Sets