Count of Substrings Containing Every Vowel and K Consonants I solution and explanation
7 more videos on this problem
Count of Substrings Containing Every Vowel and K Consonants I || LeetCode Weekly Contest 417codi · 0:50 · 1K views
Count of Substrings Containing Every Vowel and K Consonants | I & II | Leetcode 3305 | Leetcode 3306Tech Courses · 15:24 · 1K views
3305. Count of Substrings Containing Every Vowel and K Consonants I (Leetcode Medium)Programming Live with Larry · 56:41 · 586 views
Leetcode 3305 Count of Substrings Containing Every Vowel and K Consonants IThinkCode · 3:40 · 483 views
Leetcode Weekly Contest 417 | 3305. Count of Substrings Containing Every Vowel and K Consonants ICodeFod · 15:12 · 282 views
3305 Count of Substrings Containing Every Vowel and K Consonants ICodeCracker · 4:25 · 149 views
Count Of Substrings Containing Every Vowel And K Consonants IOwen Wu · 3:05 · 63 views
Count of Substrings Containing Every Vowel and K Consonants I || Leetcode Weekly Contest 417MostafaSazid · 10:44 · 56 views
The problem
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 <= 250wordconsists 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.
def is_vowel(c):
return c in 'aeiou'
def count_substrings(word, k):
vowel_count = {}
left = 0
consonant_count = 0
result = 0
vowel_mask = 0
for right in range(len(word)):
if is_vowel(word[right]):
vowel_count[word[right]] = vowel_count.get(word[right], 0) + 1
vowel_mask |= 1 << (ord(word[right]) - ord('a'))
else:
consonant_count += 1
while consonant_count > k:
if is_vowel(word[left]):
vowel_count[word[left]] -= 1
if vowel_count[word[left]] == 0:
vowel_mask &= ~(1 << (ord(word[left]) - ord('a')))
else:
consonant_count -= 1
left += 1
if vowel_mask == 31 and consonant_count == k:
result += 1
return result
print(count_substrings("ieaouqqieaouqq", 1)) # Example 3import java.util.HashMap;
public class Main {
public static void main(String[] args) {
System.out.println(countSubstrings("ieaouqqieaouqq", 1)); // Example 3
}
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static int countSubstrings(String word, int k) {
HashMap<Character, Integer> vowels = new HashMap<>();
int left = 0, consonantCount = 0, result = 0;
int vowelMask = 0;
for (int right = 0; right < word.length(); right++) {
char current = word.charAt(right);
if (isVowel(current)) {
vowels.put(current, vowels.getOrDefault(current, 0) + 1);
vowelMask |= (1 << (current - 'a'));
} else {
consonantCount++;
}
while (consonantCount > k) {
char leftChar = word.charAt(left);
if (isVowel(leftChar)) {
vowels.put(leftChar, vowels.get(leftChar) - 1);
if (vowels.get(leftChar) == 0) { vowelMask &= ~(1 << (leftChar - 'a')); }
} else {
consonantCount--;
}
left++;
}
if (vowelMask == 31 && consonantCount == k) { // 31 = 11111b for vowels
result++;
}
}
return result;
}
}#include <iostream>
#include <unordered_map>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countSubstrings(std::string word, int k) {
std::unordered_map<char, int> vowels;
int left = 0, consonantCount = 0, result = 0;
int vowelMask = 0;
for (int right = 0; right < word.size(); ++right) {
if (isVowel(word[right])) {
vowels[word[right]]++;
vowelMask |= (1 << (word[right] - 'a'));
} else {
++consonantCount;
}
while (consonantCount > k) {
if (isVowel(word[left])) {
vowels[word[left]]--;
if (vowels[word[left]] == 0) {
vowelMask &= ~(1 << (word[left] - 'a'));
}
} else {
--consonantCount;
}
++left;
}
if (vowelMask == 31 && consonantCount == k) { // 31 -> 00011111
++result;
}
}
return result;
}
int main() {
std::cout << countSubstrings("ieaouqqieaouqq", 1) << std::endl; // Example 3
return 0;
}function isVowel(c) {
return 'aeiou'.indexOf(c) !== -1;
}
function countSubstrings(word, k) {
let vowels = {};
let left = 0, consonantCount = 0, result = 0, vowelMask = 0;
for (let right = 0; right < word.length; right++) {
if (isVowel(word[right])) {
vowels[word[right]] = (vowels[word[right]] || 0) + 1;
vowelMask |= (1 << (word.charCodeAt(right) - 'a'.charCodeAt(0)));
} else {
consonantCount++;
}
while (consonantCount > k) {
if (isVowel(word[left])) {
vowels[word[left]]--;
if (vowels[word[left]] === 0) {
vowelMask &= ~(1 << (word.charCodeAt(left) - 'a'.charCodeAt(0)));
}
} else {
consonantCount--;
}
left++;
}
if (vowelMask === 31 && consonantCount === k) {
result++;
}
}
return result;
}
console.log(countSubstrings('ieaouqqieaouqq', 1)); // Example 3#include <stdio.h>
#include <string.h>
int isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countSubstrings(char* word, int k) {
int length = strlen(word);
int vowelCount[5] = {0};
int consonantCount = 0, result = 0, left = 0;
for (int right = 0; right < length; right++) {
if (isVowel(word[right])) {
int vowelIndex = word[right] - 'a';
vowelCount[vowelIndex % 5]++;
} else {
consonantCount++;
}
while (consonantCount > k) {
if (isVowel(word[left])) {
int vowelIndex = word[left] - 'a';
vowelCount[vowelIndex % 5]--;
} else {
consonantCount--;
}
left++;
}
int allVowels = 1;
for (int i = 0; i < 5; i++) {
if (vowelCount[i] == 0) {
allVowels = 0;
break;
}
}
if (allVowels && consonantCount == k) {
result++;
}
}
return result;
}
int main() {
printf("%d\n", countSubstrings("ieaouqqieaouqq", 1)); // Example 3
return 0;
}using System;
using System.Collections.Generic;
public class Program {
public static void Main() {
Console.WriteLine(CountSubstrings("ieaouqqieaouqq", 1)); // Example 3
}
public static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
public static int CountSubstrings(string word, int k) {
Dictionary<char, int> vowels = new Dictionary<char, int>();
int left = 0, consonantCount = 0, result = 0, vowelMask = 0;
for (int right = 0; right < word.Length; right++) {
if (IsVowel(word[right])) {
if (!vowels.ContainsKey(word[right])) vowels[word[right]] = 0;
vowels[word[right]]++;
vowelMask |= (1 << (word[right] - 'a'));
} else {
consonantCount++;
}
while (consonantCount > k) {
if (IsVowel(word[left])) {
vowels[word[left]]--;
if (vowels[word[left]] == 0) vowelMask &= ~(1 << (word[left] - 'a'));
} else {
consonantCount--;
}
left++;
}
if (vowelMask == 31 && consonantCount == k) { // 31 = 11111b
result++;
}
}
return result;
}
}The Python function count_substrings employs a sliding window approach to identify and count valid substrings. It keeps track of vowels using a dictionary and uses a bitmask to verify the presence of all vowels, providing a float operation of consonant count.
Time Complexity: O(n), where n is the word's length, through optimized sliding with minimal passes.
Space Complexity: O(1), fixed additional space is utilized for tracking vowels and consonant-related data without depending on input size.
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.
def is_vowel(c):
return c in 'aeiou'
def count_substrings(word, k):
length = len(word)
result = 0
for start in range(length):
vowels = [0] * 5
consonants = 0
for end in range(start, length):
if is_vowel(word[end]):
vowels[ord(word[end]) - ord('a')] += 1
else:
consonants += 1
all_vowels = all(x > 0 for x in vowels)
if all_vowels and consonants == k:
result += 1
return result
print(count_substrings('ieaouqqieaouqq', 1)) # Example 3public class Main {
public static void main(String[] args) {
System.out.println(countSubstrings("ieaouqqieaouqq", 1)); // Example 3
}
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static int countSubstrings(String word, int k) {
int length = word.length();
int result = 0;
for (int start = 0; start < length; start++) {
int[] vowels = new int[5];
int consonants = 0;
for (int end = start; end < length; end++) {
if (isVowel(word.charAt(end))) {
vowels[word.charAt(end) - 'a']++;
} else {
consonants++;
}
boolean allVowels = true;
for (int count : vowels) {
if (count == 0) {
allVowels = false;
break;
}
}
if (allVowels && consonants == k) {
result++;
}
}
}
return result;
}
}#include <iostream>
#include <string>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countSubstrings(std::string word, int k) {
int length = word.size();
int result = 0;
for (int start = 0; start < length; ++start) {
int vowels[5] = {0};
int consonants = 0;
for (int end = start; end < length; ++end) {
if (isVowel(word[end])) {
vowels[word[end] - 'a']++;
} else {
consonants++;
}
bool allVowels = true;
for (int count : vowels) {
allVowels &= (count > 0);
}
if (allVowels && consonants == k) {
result++;
}
}
}
return result;
}
int main() {
std::cout << countSubstrings("ieaouqqieaouqq", 1) << std::endl; // Example 3
return 0;
}function isVowel(c) {
return 'aeiou'.indexOf(c) !== -1;
}
function countSubstrings(word, k) {
let length = word.length;
let result = 0;
for (let start = 0; start < length; start++) {
let vowels = new Array(5).fill(0);
let consonants = 0;
for (let end = start; end < length; end++) {
if (isVowel(word[end])) {
vowels[word.charCodeAt(end) - 'a'.charCodeAt(0)]++;
} else {
consonants++;
}
let allVowels = vowels.every(count => count > 0);
if (allVowels && consonants === k) {
result++;
}
}
}
return result;
}
console.log(countSubstrings('ieaouqqieaouqq', 1)); // Example 3#include <stdio.h>
#include <string.h>
int isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int countSubstrings(char* word, int k) {
int length = strlen(word);
int result = 0;
for (int start = 0; start < length; start++) {
int vowels[5] = {0};
int consonants = 0;
for (int end = start; end < length; end++) {
if (isVowel(word[end])) {
int vowelIndex = word[end] - 'a';
vowels[vowelIndex % 5]++;
} else {
consonants++;
}
int allVowels = 1;
for (int i = 0; i < 5; i++) {
if (vowels[i] == 0) {
allVowels = 0;
break;
}
}
if (allVowels && consonants == k) {
result++;
}
}
}
return result;
}
int main() {
printf("%d\n", countSubstrings("ieaouqqieaouqq", 1)); // Example 3
return 0;
}using System;
public class Program {
public static void Main() {
Console.WriteLine(CountSubstrings("ieaouqqieaouqq", 1)); // Example 3
}
public static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
public static int CountSubstrings(string word, int k) {
int length = word.Length;
int result = 0;
for (int start = 0; start < length; start++) {
int[] vowels = new int[5];
int consonants = 0;
for (int end = start; end < length; end++) {
if (IsVowel(word[end])) {
vowels[word[end] - 'a']++;
} else {
consonants++;
}
bool allVowels = true;
foreach (int count in vowels) {
if (count == 0) {
allVowels = false;
break;
}
}
if (allVowels && consonants == k) {
result++;
}
}
}
return result;
}
}The Python code checks each eligible substring for all vowels' presence and a specific consonant tally. The simplistic and comprehensive, albeit inefficient, processing offers integration yet prognostically negligible for larger scales because of its brute force underpinnings.
Time Complexity: O(n^3), underlying highly repetitive span-netting by suspected complete explicit invocation.
Space Complexity: O(1), minimal constant space-usage over extensive singular computation.
Approach 3: Problem Transformation + Sliding Window
We can transform the problem into solving the following two subproblems:
- Find the total number of substrings where each vowel appears at least once and contains at least
kconsonants, denoted asf(k); - Find the total number of substrings where each vowel appears at least once and contains at least
k + 1consonants, denoted asf(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).
function countOfSubstrings(word: string, k: number): number {
const f = (k: number): number => {
let ans = 0;
let l = 0,
x = 0;
const cnt = new Map<string, number>();
const vowel = (c: string): boolean => {
return c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u';
};
for (const c of word) {
if (vowel(c)) {
cnt.set(c, (cnt.get(c) || 0) + 1);
} else {
x++;
}
while (x >= k && cnt.size === 5) {
const d = word[l++];
if (vowel(d)) {
cnt.set(d, cnt.get(d)! - 1);
if (cnt.get(d) === 0) {
cnt.delete(d);
}
} else {
x--;
}
}
ans += l;
}
return ans;
};
return f(k) - f(k + 1);
}func countOfSubstrings(word string, k int) int {
f := func(k int) int {
var ans int = 0
l, x := 0, 0
cnt := make(map[rune]int)
vowel := func(c rune) bool {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}
for _, c := range word {
if vowel(c) {
cnt[c]++
} else {
x++
}
for x >= k && len(cnt) == 5 {
d := rune(word[l])
l++
if vowel(d) {
cnt[d]--
if cnt[d] == 0 {
delete(cnt, d)
}
} else {
x--
}
}
ans += l
}
return ans
}
return f(k) - f(k+1)
}impl Solution {
pub fn count_of_substrings(word: String, k: i32) -> i32 {
fn f(word: &Vec<char>, k: i32) -> i32 {
let mut ans = 0;
let mut l = 0;
let mut x = 0;
let mut cnt = std::collections::HashMap::new();
let is_vowel = |c: char| matches!(c, 'a' | 'e' | 'i' | 'o' | 'u');
for (r, &c) in word.iter().enumerate() {
if is_vowel(c) {
*cnt.entry(c).or_insert(0) += 1;
} else {
x += 1;
}
while x >= k && cnt.len() == 5 {
let d = word[l];
l += 1;
if is_vowel(d) {
let count = cnt.entry(d).or_insert(0);
*count -= 1;
if *count == 0 {
cnt.remove(&d);
}
} else {
x -= 1;
}
}
ans += l as i32;
}
ans
}
let chars: Vec<char> = word.chars().collect();
f(&chars, k) - f(&chars, k + 1)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the word's length, through optimized sliding with minimal passes. |
| Brute Force Approach | Time Complexity: O(n^3), underlying highly repetitive span-netting by suspected complete explicit invocation. |
| Problem Transformation + Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n²) | O(1) | Good for understanding the constraints and verifying logic on small inputs. |
| Sliding Window with Vowel Frequency | O(n) | O(1) | Best for large strings. Uses two pointers and frequency tracking to count valid substrings efficiently. |
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.