Count Vowel Substrings of a String - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

EasyHash Table String17 min readAsked at: Amazon, Microsoft, Wells Fargo +9

Practice this problem

Problem Statement

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 <= 100
word consists 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(n²), 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.

The solution in C involves two nested loops to iterate over all possible substrings. Each substring is then checked for the presence of all five vowels using the helper function 'containsAllVowels'. The 'isVowel' function helps in determining if a character is part of the vowels.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^3) due to the triply nested loop structure.
Space Complexity: O(1) as only a fixed-size array is used to check vowels.

Try this approach in the editor →

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.

The C implementation uses a sliding window to efficiently manage the range in which all vowels appear. When a non-vowel is encountered, the state is reset, improving performance over analyzing static substrings.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) compared to the traditional O(n^3).
Space Complexity: O(1).

Try this approach in the editor →

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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n^3) due to the triply nested loop structure. Space Complexity: O(1) as only a fixed-size array is used to check vowels.
Sliding Window Approach	Time Complexity: O(n) compared to the traditional O(n^3). Space Complexity: O(1).
Brute Force Enumeration + Hash Table	—

Detailed 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

Video Solution

2062. Count Vowel Substrings of a String | LEETCODE EASY • code Explainer • 4,470 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Vowel Substrings of a String with our built-in code editor and test cases.

Practice on FleetCode

Count of Substrings Containing Every Vowel and K Consonants I

Count of Substrings Containing Every Vowel and K Consonants II

Problem Info

DifficultyEasy

Acceptance73.6%

Approaches3

Reading time17 min

Asked at

Amazon Microsoft Wells Fargo Oracle Salesforce

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Brute Force Approach

Code

Complexity

Approach 2: Sliding Window Approach

Code

Complexity

Approach 3: Brute Force Enumeration + Hash Table

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents