Count Vowel Substrings of a String solution and explanation
Google
9 more videos on this problem
2062. Count Vowel Substrings of a String | LEETCODE EASYcode Explainer · 6:32 · 4K views
2062. Count Vowel Substrings of a String (Leetcode Easy)Programming Live with Larry · 5:29 · 4K views
2062. Count Vowel Substrings of a StringMath Geeks · 2:24 · 1K views
Leetcode | Easy | 2062. Count Vowel Substrings of a String | Two Pointers | Time: O(N) | JavascriptSoftware Interviews Prep · 13:43 · 1K views
LeetCode#2062 Count Vowel Substrings of a String - PythonCodeJulian · 2:54 · 554 views
#LeetCode 2062 | Count Vowel Substrings of a String #JavaSleepy Cracker · 11:06 · 445 views
Count Vowel Substrings Of A StringOwen Wu · 2:25 · 404 views
🄵🄰🄸🄻 Leetcode 2062 Count Vowel Substrings of a String 🏎️ IN ⚡️⚡️⚡️ L I N E A R T I M E 💨Pass OR Fail: Coding Journey · 36:17 · 394 views
2062. Count Vowel Substrings of a String #faangprep #codeprep #leetcodedailychallenge #approachSharda Learning Center · 0:59 · 204 views
Day 337: LeetCode Problem 2062. Count Vowel Substrings of a String - SwiftiOSxBank · 8:51 · 173 views
The problem
A substring is a contiguous (non-empty) sequence of characters within a string.
A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.
Given a string word, return the number of vowel substrings in word.
Example 1:
Input: word = "aeiouu" Output: 2 Explanation: The vowel substrings of word are as follows (underlined): - "aeiouu" - "aeiouu"
Example 2:
Input: word = "unicornarihan" Output: 0 Explanation: Not all 5 vowels are present, so there are no vowel substrings.
Example 3:
Input: word = "cuaieuouac" Output: 7 Explanation: The vowel substrings of word are as follows (underlined): - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac"
Constraints:
1 <= word.length <= 100wordconsists of lowercase English letters only.
Approach overview
Problem Overview: You are given a string and need to count substrings that contain only vowels (a, e, i, o, u) and include all five vowels at least once. Any substring containing a consonant is invalid, so valid substrings must be continuous vowel segments that contain the full vowel set.
Approach 1: Brute Force Enumeration (Time: O(n2), Space: O(1))
Iterate over every possible starting index and expand the substring one character at a time. While expanding, stop immediately if you hit a consonant because the substring can no longer be valid. Track vowels using a small frequency array or a hash set. Whenever the set size becomes five, the current substring contains all vowels and contributes to the count. This approach is straightforward and helps verify correctness, but it checks many overlapping substrings.
The key observation is that valid substrings must be entirely composed of vowels. As soon as a consonant appears, the expansion stops and the next starting index is tested. Even though the logic is simple, nested iteration makes the runtime quadratic in the worst case when the string contains long vowel segments.
Approach 2: Sliding Window with Vowel Frequency (Time: O(n), Space: O(1))
The optimal solution scans the string using a sliding window. Maintain two pointers that define a window containing only vowels. Use a small frequency map (or array indexed by vowel) to track how many of each vowel appears in the current window. If a consonant appears, reset the window because valid substrings cannot cross consonants.
As the window expands, update the vowel counts and track how many distinct vowels are present. When all five vowels exist in the window, every valid prefix of the window also forms a valid substring. By adjusting the left pointer while maintaining the vowel requirement, you can count multiple substrings efficiently. Each character enters and leaves the window at most once, giving linear time complexity.
This technique is a common pattern for substring counting problems involving constraints on characters. It relies on constant‑size tracking structures and pointer movement rather than repeatedly rebuilding substrings.
Recommended for interviews: Start by describing the brute force substring enumeration to demonstrate understanding of the constraints. Then move to the optimized sliding window solution. Interviewers typically expect the linear scan because it shows familiarity with substring problems involving string processing and character tracking using a hash table or frequency array.
Approach 1: Brute Force Approach
This approach involves iterating over all possible substrings of the given string and checking if each substring contains all the vowels ('a', 'e', 'i', 'o', 'u'). This is a straightforward method but not optimized due to the nested loop structure.
def contains_all_vowels(sub):
return len(set(sub) & set('aeiou')) == 5
def count_vowel_substrings(word):
count = 0
for start in range(len(word)):
for end in range(start, len(word)):
sub = word[start:end + 1]
if all(c in 'aeiou' for c in sub) and contains_all_vowels(sub):
count += 1
return count
print(count_vowel_substrings("aeiouu"))
print(count_vowel_substrings("unicornarihan"))
print(count_vowel_substrings("cuaieuouac"))import java.util.HashSet;
import java.util.Set;
public class VowelSubstrings {
public static boolean containsAllVowels(String str) {
Set<Character> vowels = new HashSet<>();
for (char c : str.toCharArray()) {
if ('a' == c || 'e' == c || 'i' == c || 'o' == c || 'u' == c) {
vowels.add(c);
}
}
return vowels.size() == 5;
}
public static int countVowelSubstrings(String word) {
int count = 0;
for (int i = 0; i < word.length(); i++) {
for (int j = i; j < word.length(); j++) {
String sub = word.substring(i, j + 1);
if (containsAllVowels(sub)) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
System.out.println(countVowelSubstrings("aeiouu"));
System.out.println(countVowelSubstrings("unicornarihan"));
System.out.println(countVowelSubstrings("cuaieuouac"));
}
}#include <iostream>
#include <string>
#include <unordered_set>
bool containsAllVowels(const std::string& str) {
std::unordered_set<char> vowels;
for (char c : str) {
if (strchr("aeiou", c)) {
vowels.insert(c);
}
}
return vowels.size() == 5;
}
int countVowelSubstrings(const std::string& word) {
int count = 0;
for (size_t i = 0; i < word.size(); ++i) {
for (size_t j = i; j < word.size(); ++j) {
std::string sub = word.substr(i, j - i + 1);
if (containsAllVowels(sub)) {
++count;
}
}
}
return count;
}
int main() {
std::cout << countVowelSubstrings("aeiouu") << std::endl;
std::cout << countVowelSubstrings("unicornarihan") << std::endl;
std::cout << countVowelSubstrings("cuaieuouac") << std::endl;
return 0;
}function containsAllVowels(sub) {
let vowels = new Set();
for (let char of sub) {
if ('aeiou'.includes(char)) {
vowels.add(char);
}
}
return vowels.size === 5;
}
function countVowelSubstrings(word) {
let count = 0;
for (let i = 0; i < word.length; i++) {
for (let j = i; j < word.length; j++) {
let sub = word.substring(i, j + 1);
if ([...sub].every(c => 'aeiou'.includes(c)) && containsAllVowels(sub)) {
count++;
}
}
}
return count;
}
console.log(countVowelSubstrings("aeiouu"));
console.log(countVowelSubstrings("unicornarihan"));
console.log(countVowelSubstrings("cuaieuouac"));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
bool containsAllVowels(char *sub, int subLength) {
bool vowels[5] = {0};
for (int i = 0; i < subLength; i++) {
if (sub[i] == 'a') vowels[0] = true;
if (sub[i] == 'e') vowels[1] = true;
if (sub[i] == 'i') vowels[2] = true;
if (sub[i] == 'o') vowels[3] = true;
if (sub[i] == 'u') vowels[4] = true;
}
for (int i = 0; i < 5; i++) {
if (!vowels[i]) return false;
}
return true;
}
int countVowelSubstrings(char *word) {
int count = 0;
int length = strlen(word);
for (int start = 0; start < length; start++) {
for (int end = start + 1; end <= length; end++) {
bool isValid = true;
for (int i = start; i < end; i++) {
if (!isVowel(word[i])) {
isValid = false;
break;
}
}
if (isValid && containsAllVowels(word + start, end - start)) {
count++;
}
}
}
return count;
}
int main() {
printf("%d\n", countVowelSubstrings("aeiouu"));
printf("%d\n", countVowelSubstrings("unicornarihan"));
printf("%d\n", countVowelSubstrings("cuaieuouac"));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static bool ContainsAllVowels(string sub) {
HashSet<char> vowels = new HashSet<char>();
foreach (char c in sub) {
if ("aeiou".Contains(c)) {
vowels.Add(c);
}
}
return vowels.Count == 5;
}
static int CountVowelSubstrings(string word) {
int count = 0;
for (int i = 0; i < word.Length; i++) {
for (int j = i; j < word.Length; j++) {
string sub = word.Substring(i, j - i + 1);
if (ContainsAllVowels(sub)) {
count++;
}
}
}
return count;
}
static void Main(string[] args) {
Console.WriteLine(CountVowelSubstrings("aeiouu"));
Console.WriteLine(CountVowelSubstrings("unicornarihan"));
Console.WriteLine(CountVowelSubstrings("cuaieuouac"));
}
}The Python implementation uses list comprehensions and set intersections to determine if a substring contains all vowels. It checks every possible substring within the input word, ensuring it contains only vowels and all five are present.
Time Complexity: O(n^3) due to nested loops and substring checks.
Space Complexity: O(1).
Approach 2: Sliding Window Approach
This approach leverages a sliding window mechanism to efficiently find substrings containing all vowels. By keeping track of the vowel count, the window can be expanded and contracted to find matches, significantly reducing unnecessary duplicate work.
def count_vowel_substrings(word):
left = 0
count = 0
vowels = set()
for right in range(len(word)):
if word[right] in 'aeiou':
vowels.add(word[right])
while len(vowels) == 5:
count += right - left + 1
vowels.remove(word[left])
left += 1
else:
vowels.clear()
left = right + 1
return count
print(count_vowel_substrings("aeiouu"))
print(count_vowel_substrings("unicornarihan"))
print(count_vowel_substrings("cuaieuouac"))import java.util.HashSet;
import java.util.Set;
public class VowelSubstrings {
public static int countVowelSubstrings(String word) {
int count = 0, left = 0, right = 0;
Set<Character> vowels = new HashSet<>();
while (right < word.length()) {
if ("aeiou".indexOf(word.charAt(right)) != -1) {
vowels.add(word.charAt(right));
while (vowels.size() == 5) {
count += right - left + 1;
vowels.remove(word.charAt(left++));
}
} else {
vowels.clear();
left = right + 1;
}
right++;
}
return count;
}
public static void main(String[] args) {
System.out.println(countVowelSubstrings("aeiouu"));
System.out.println(countVowelSubstrings("unicornarihan"));
System.out.println(countVowelSubstrings("cuaieuouac"));
}
}#include <iostream>
#include <unordered_set>
using namespace std;
int countVowelSubstrings(string word) {
int left = 0, right = 0, count = 0;
unordered_set<char> vowels;
while (right < word.size()) {
if (strchr("aeiou", word[right])) {
vowels.insert(word[right]);
while (vowels.size() == 5) {
count += right - left + 1;
vowels.erase(word[left++]);
}
} else {
vowels.clear();
left = right + 1;
}
right++;
}
return count;
}
int main() {
cout << countVowelSubstrings("aeiouu") << endl;
cout << countVowelSubstrings("unicornarihan") << endl;
cout << countVowelSubstrings("cuaieuouac") << endl;
return 0;
}function countVowelSubstrings(word) {
let left = 0;
let count = 0;
let vowels = new Set();
for (let right = 0; right < word.length; right++) {
if ('aeiou'.includes(word[right])) {
vowels.add(word[right]);
while (vowels.size === 5) {
count += right - left + 1;
vowels.delete(word[left++]);
}
} else {
vowels.clear();
left = right + 1;
}
}
return count;
}
console.log(countVowelSubstrings("aeiouu"));
console.log(countVowelSubstrings("unicornarihan"));
console.log(countVowelSubstrings("cuaieuouac"));#include <stdio.h>
#include <string.h>
int countVowelSubstrings(char *word) {
int vowelCount[128] = {0};
int uniqueVowels = 0;
int left = 0;
int count = 0;
for (int right = 0; word[right] != '\0'; right++) {
if (strchr("aeiou", word[right])) {
if (!vowelCount[word[right]]++) uniqueVowels++;
while (uniqueVowels == 5) {
count++;
if (!--vowelCount[word[left++]]) uniqueVowels--;
}
} else {
memset(vowelCount, 0, sizeof(vowelCount));
uniqueVowels = 0;
left = right + 1;
}
}
return count;
}
int main() {
printf("%d\n", countVowelSubstrings("aeiouu"));
printf("%d\n", countVowelSubstrings("unicornarihan"));
printf("%d\n", countVowelSubstrings("cuaieuouac"));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int CountVowelSubstrings(string word) {
int count = 0, left = 0;
HashSet<char> vowels = new HashSet<char>();
for (int right = 0; right < word.Length; right++) {
char c = word[right];
if ("aeiou".Contains(c)) {
vowels.Add(c);
while (vowels.Count == 5) {
count += right - left + 1;
vowels.Remove(word[left]);
left++;
}
} else {
vowels.Clear();
left = right + 1;
}
}
return count;
}
static void Main(string[] args) {
Console.WriteLine(CountVowelSubstrings("aeiouu"));
Console.WriteLine(CountVowelSubstrings("unicornarihan"));
Console.WriteLine(CountVowelSubstrings("cuaieuouac"));
}
}This Python program optimally handles substring discovery through dynamic window adjustments, well-suited for consistent achievements of counting whenever all vowels are present.
Time Complexity: O(n), with space efficiency in mind.
Space Complexity: O(1).
Approach 3: Brute Force Enumeration + Hash Table
We can enumerate the left endpoint i of the substring. For the current left endpoint, maintain a hash table to record the vowels that appear in the current substring. Then enumerate the right endpoint j. If the character at the current right endpoint is not a vowel, break the loop. Otherwise, add the character at the current right endpoint to the hash table. If the number of elements in the hash table is 5, it means the current substring is a vowel substring, and increment the result by 1.
The time complexity is O(n^2), and the space complexity is O(C). Here, n is the length of the string word, and C is the size of the character set, which is 5 in this problem.
function countVowelSubstrings(word: string): number {
let ans = 0;
const n = word.length;
for (let i = 0; i < n; ++i) {
const t = new Set<string>();
for (let j = i; j < n; ++j) {
const c = word[j];
if (!(c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u')) {
break;
}
t.add(c);
if (t.size === 5) {
ans++;
}
}
}
return ans;
}func countVowelSubstrings(word string) int {
ans, n := 0, len(word)
for i := range word {
t := map[byte]bool{}
for j := i; j < n; j++ {
c := word[j]
if !(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
break
}
t[c] = true
if len(t) == 5 {
ans++
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) due to nested loops and substring checks. |
| Sliding Window Approach | Time Complexity: O(n), with space efficiency in mind. |
| Brute Force Enumeration + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem and verifying logic on small inputs |
| Sliding Window with Vowel Frequency | O(n) | O(1) | Preferred solution for large strings and typical interview expectations |
Frequently asked questions
Is Count Vowel Substrings of a String easy or hard?
This problem is generally classified as Easy because the constraints are small and the brute force solution is straightforward. The challenge comes from recognizing that only vowel segments matter and applying a sliding window to optimize the counting process. Understanding this pattern helps with many medium-level string problems.
Count Vowel Substrings of a String Python/Java solution
In Python and Java, the common implementation uses a sliding window with a dictionary or array to store vowel counts. As the right pointer expands the window, update counts and track distinct vowels. When all five vowels exist, adjust the left pointer and count valid substrings. The algorithm runs in O(n) time and O(1) space.
How to solve Count Vowel Substrings of a String in O(n)?
Use a sliding window that expands while characters are vowels. Maintain counts for the five vowels and track how many distinct vowels are currently present. When the window contains all five vowels, count valid substrings while adjusting the left pointer to maintain the condition. Reset the window whenever a consonant appears.
What is the best approach for Count Vowel Substrings of a String?
The sliding window approach is the most efficient method. It scans the string once while maintaining a window that contains only vowels and tracking the frequency of each vowel. When all five vowels appear in the window, valid substrings can be counted efficiently. This reduces the complexity to O(n) time with O(1) extra space.
Is Count Vowel Substrings of a String asked at Google/Amazon/Meta?
Substring counting and sliding window problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of tracking character frequencies within a window is a common interview topic. Practicing problems like this strengthens core string and two‑pointer skills.
What data structure is used in Count Vowel Substrings of a String?
Most solutions use a small frequency map or array to track occurrences of the five vowels. This structure behaves like a lightweight hash table with constant size. Combined with two pointers for the sliding window, it allows efficient substring validation and counting.
What is the time complexity of Count Vowel Substrings of a String?
The optimal sliding window solution runs in O(n) time because each character is processed at most twice by the two pointers. The brute force approach that checks every substring runs in O(n²) time in the worst case when the string contains long sequences of vowels. Space complexity for both methods is O(1) since only a small vowel frequency structure is used.