Skip to main content
Talentd

Count of Substrings Containing Every Vowel and K Consonants I - Solution & Explanation

MediumHash TableStringSliding Window25 min read
Practice this problem

Problem Statement

You are given a string word and a non-negative integer k.

Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

 

Example 1:

Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

Input: word = "aeiou", k = 0

Output: 1

Explanation:

The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".

Example 3:

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

  • word[0..5], which is "ieaouq".
  • word[6..11], which is "qieaou".
  • word[7..12], which is "ieaouq".

 

Constraints:

  • 5 <= word.length <= 250
  • word consists only of lowercase English letters.
  • 0 <= k <= word.length - 5

Approach Overview

Problem Overview: Given a string word and an integer k, count how many substrings contain every vowel (a, e, i, o, u) at least once and exactly k consonants. You need to scan all possible substrings but avoid the naive O(n²) enumeration when possible.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Start every substring at index i and extend it one character at a time to index j. Maintain a small frequency map for vowels and a counter for consonants while expanding the substring. Each step checks whether all five vowels appear at least once and whether the consonant count equals k. Since there are O(n²) substrings and each extension performs constant-time updates, the total time complexity is O(n²) with O(1) auxiliary space (only five vowel counters and a consonant counter). This approach is straightforward and useful for verifying correctness or handling small inputs, but it becomes slow for large strings.

Approach 2: Sliding Window with Vowel Tracking (O(n) time, O(1) space)

The optimal strategy uses a sliding window with two pointers. Expand the right pointer while maintaining a vowel frequency map using a small hash table and a counter for consonants. The key observation: once a window contains all five vowels and satisfies the consonant constraint, every valid extension contributes additional substrings. To handle the "exactly k consonants" requirement efficiently, compute substrings with atMost(k) consonants and subtract those with atMost(k-1). While moving the window, update vowel frequencies and shrink from the left whenever the consonant limit is exceeded. Each character enters and leaves the window at most once, giving O(n) time complexity and constant extra space.

This method relies on fast membership checks for vowels and maintaining counts for characters in the current window. Because the alphabet is small, the memory footprint stays constant. Combining the sliding window with vowel coverage tracking avoids scanning the same substring multiple times.

Recommended for interviews: The brute force solution demonstrates that you understand the substring constraints and how to track vowel presence. Interviewers typically expect the optimized sliding window approach with a small string frequency structure. It reduces the complexity from O(n²) to O(n), which shows strong pattern recognition for substring counting problems.

Approach 1: Sliding Window Approach

This approach involves the use of a sliding window to efficiently traverse the string and count valid substrings. We maintain two pointers defining the window and use data structures to track vowels and consonant counts within the window.

This code defines a function countSubstrings which calculates the number of substrings containing every vowel and exactly k consonants using a sliding window approach. The function tracks the number of vowels and consonants within the current window using arrays and counters. Upon matching the criteria (all vowels present, exactly k consonants), it increments the result count.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the word. The algorithm effectively slides through the string once using two pointers.
Space Complexity: O(1), since we use constant additional space for the arrays and counters regardless of the input size.

Try this approach in the editor →

Approach 2: Brute Force Approach

The brute force approach involves checking each substring of the input string and verifying if it contains all vowels and exactly k consonants. This method is less efficient and serves as a baseline.

This brute force implementation assesses every substring and checks if it contains all vowels and exactly k consonants. While straightforward, it iteratively computes presence for each new substring, making it computationally expensive.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), where n is the length of the word, as it checks all possible substrings on possibly full scans for vowels and consonants.
Space Complexity: O(1), employing constant space but with inefficient time overhead.

Try this approach in the editor →

Approach 3: Problem Transformation + Sliding Window

We can transform the problem into solving the following two subproblems:

  1. Find the total number of substrings where each vowel appears at least once and contains at least k consonants, denoted as f(k);
  2. Find the total number of substrings where each vowel appears at least once and contains at least k + 1 consonants, denoted as f(k + 1).

Then the answer is f(k) - f(k + 1).

Therefore, we design a function f(k) to count the total number of substrings where each vowel appears at least once and contains at least k consonants.

We can use a hash table cnt to count the occurrences of each vowel, a variable ans to store the answer, a variable l to record the left boundary of the sliding window, and a variable x to record the number of consonants in the current window.

Traverse the string. If the current character is a vowel, add it to the hash table cnt; otherwise, increment x by one. If x \ge k and the size of the hash table cnt is 5, it means the current window meets the conditions. We then move the left boundary in a loop until the window no longer meets the conditions. At this point, all substrings ending at the right boundary r and with the left boundary in the range [0, .. l - 1] meet the conditions, totaling l substrings. We add l to the answer. Continue traversing the string until the end, and we get f(k).

Finally, we return f(k) - f(k + 1).

The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n), where n is the length of the word. The algorithm effectively slides through the string once using two pointers.
Space Complexity: O(1), since we use constant additional space for the arrays and counters regardless of the input size.

Brute Force Approach

Time Complexity: O(n^3), where n is the length of the word, as it checks all possible substrings on possibly full scans for vowels and consonants.
Space Complexity: O(1), employing constant space but with inefficient time overhead.

Problem Transformation + Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n²)O(1)Good for understanding the constraints and verifying logic on small inputs.
Sliding Window with Vowel FrequencyO(n)O(1)Best for large strings. Uses two pointers and frequency tracking to count valid substrings efficiently.

Video Solution

Count of Substrings Containing Every Vowel and K Consonants I || LeetCode Weekly Contest 417 • codi • 1,862 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Count of Substrings Containing Every Vowel and K Consonants I easy or hard?
The problem is rated Medium because it combines multiple string techniques. You must track vowel presence, maintain a consonant constraint, and apply the sliding window pattern correctly. Once the at-most counting trick is recognized, the implementation becomes manageable.
Count of Substrings Containing Every Vowel and K Consonants I Python/Java solution
Python and Java implementations typically use two pointers and a frequency map for vowels. Each iteration updates counts as the window expands or shrinks, ensuring all five vowels appear and the consonant count matches the constraint. The algorithm runs in O(n) time and uses constant extra memory.
How to solve Count of Substrings Containing Every Vowel and K Consonants I in O(n)?
Use a sliding window with two pointers and track vowel counts using a small hash map or array. Expand the window while counting consonants, and shrink it when the consonant limit is exceeded. Count substrings with at most k consonants and subtract those with at most k-1 to obtain substrings with exactly k consonants and all five vowels.
What is the best approach for Count of Substrings Containing Every Vowel and K Consonants I?
The sliding window approach is the most efficient solution. It maintains a moving window with two pointers while tracking vowel frequencies and the number of consonants. By counting substrings with at most k consonants and subtracting those with at most k-1, you can compute the exact count in O(n) time with O(1) space.
Is Count of Substrings Containing Every Vowel and K Consonants I asked at Google/Amazon/Meta?
Problems combining substring counting, vowel tracking, and sliding window techniques are common in interviews at companies like Amazon, Google, and Meta. Variations frequently appear where candidates must maintain character frequency constraints while scanning strings efficiently.
What data structure is used in Count of Substrings Containing Every Vowel and K Consonants I?
The main data structure is a small hash table or fixed-size array used to track vowel frequencies inside the current window. Combined with the sliding window technique and counters for consonants, it allows constant-time updates while scanning the string.
What is the time complexity of Count of Substrings Containing Every Vowel and K Consonants I?
The optimal solution runs in O(n) time using a sliding window, because each character enters and leaves the window at most once. Space complexity remains O(1) since only five vowel counters and a few integers are stored. A brute force approach would take O(n²) time by checking every substring.

Ready to solve this problem?

Practice Count of Substrings Containing Every Vowel and K Consonants I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Vowel Substrings of a String

Next

Longest Substring Of All Vowels in Order