Count of Substrings Containing Every Vowel and K Consonants II
MedPrompt
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 <= 2 * 105wordconsists only of lowercase English letters.0 <= k <= word.length - 5
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward way to solve this problem is to check every single substring of the input word. We can generate all substrings, and for each one, we verify if it contains all five vowels ('a', 'e', 'i', 'o', 'u') and exactly k consonants.
Algorithm
- Generate all possible substrings of the
wordusing two nested loops. The outer loopiiterates from0ton-1(start of the substring), and the inner loopjiterates fromiton-1(end of the substring). - For each substring
word[i..j], create a helper function to check if it meets the criteria. - The helper function will iterate through the characters of the substring.
- Inside the helper function, use a frequency map or a set to count the number of distinct vowels and a separate counter for consonants.
- After iterating through the substring, check if the number of distinct vowels is exactly 5 and the number of consonants is exactly
k. - If both conditions are met, increment a global counter.
- Return the global counter after checking all substrings.
Walkthrough
This approach involves a triply nested loop structure. The outer two loops define the start (i) and end (j) indices of a substring. The third, inner loop (or a function call that implies a loop) iterates over this substring word[i..j] to count its vowels and consonants. A set is used to keep track of the unique vowels encountered to ensure all five are present. If a substring satisfies both conditions (5 unique vowels and k consonants), we increment our result counter.
class Solution { private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public long beautifulSubstrings(String word, int k) { long count = 0; int n = word.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Check substring word[i..j] Set<Character> vowels = new HashSet<>(); int consonants = 0; for (int l = i; l <= j; l++) { char c = word.charAt(l); if (isVowel(c)) { vowels.add(c); } else { consonants++; } } if (vowels.size() == 5 && consonants == k) { count++; } } } return count; }}Complexity
Time
O(N³), where N is the length of the string. There are O(N²) substrings, and checking each one takes O(N) time. This is too slow for the given constraints.
Space
O(1), as the set for vowels will hold at most 5 elements.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient and will not pass the time limits for the given constraints.
Redundant computations as information about overlapping substrings is not reused.
We can optimize the brute-force approach by avoiding the repeated scanning of substrings. Instead of re-calculating the vowel and consonant counts for each substring from scratch, we can fix the starting point of a substring and extend it one character at a time, updating the counts incrementally.
Algorithm
- Use two nested loops. The outer loop
ifixes the starting index of the substring. - The inner loop
jextends the substring by one character at a time, starting fromi. - For each starting index
i, initialize a vowel set and a consonant counter. - As the inner loop pointer
jmoves fromiton-1, update the vowel set and consonant count for the current substringword[i..j]based on the characterword.charAt(j). - After each update, check if the vowel set size is 5 and the consonant count is
k. - If the conditions are met, increment the total count of beautiful substrings.
- Repeat for all starting indices
i.
Walkthrough
This method reduces one level of looping from the naive brute-force approach. We iterate through all possible starting positions i of a substring. For each i, we iterate from j = i to the end of the string. We maintain the counts of distinct vowels and consonants for the substring word[i..j]. When we extend the substring to word[i..j+1], we just need to account for the new character word.charAt(j+1). This avoids the third loop for checking the substring property, bringing the complexity down.
class Solution { private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public long beautifulSubstrings(String word, int k) { long count = 0; int n = word.length(); for (int i = 0; i < n; i++) { Set<Character> vowels = new HashSet<>(); int consonants = 0; for (int j = i; j < n; j++) { char c = word.charAt(j); if (isVowel(c)) { vowels.add(c); } else { consonants++; } if (vowels.size() == 5 && consonants == k) { count++; } } } return count; }}Complexity
Time
O(N²), where N is the length of the string. We have two nested loops. This will time out given the constraints.
Space
O(1), as the vowel set stores at most 5 elements.
Trade-offs
Pros
More efficient than the naive O(N³) brute-force approach.
Still relatively easy to understand.
Cons
Still too slow for the given constraints as it has a quadratic time complexity.
The most efficient solution uses a sliding window technique with multiple pointers. The main idea is to fix the right endpoint of a substring and efficiently count the number of valid left endpoints. A substring is valid if it satisfies two conditions: containing all five vowels and having exactly k consonants. We can find the range of valid start indices for each condition separately and then find their intersection.
Algorithm
- The core idea is to iterate through the string with a right pointer
jand, for eachj, count how many valid left pointersiexist. - A substring
word[i..j]is valid if it has all 5 vowels and exactlykconsonants. - We can rephrase the consonant condition: the number of consonants is at most
kAND not at mostk-1. - We use three left pointers:
p_vowel,p_k, andp_k_minus_1, which slide along with the right pointerj. - For each
j: a.p_kis advanced such that the window[p_k, j]has at mostkconsonants. b.p_k_minus_1is advanced such that[p_k_minus_1, j]has at mostk-1consonants. This means any valid startifor the consonant condition must be in the range[p_k, p_k_minus_1 - 1]. c.p_vowelis advanced such that[p_vowel-1, j]is the shortest suffix of[0, j]containing all 5 vowels. This means any valid startifor the vowel condition must bei < p_vowel. - The number of valid start indices
ifor the currentjis the size of the intersection of these two ranges:[p_k, p_k_minus_1 - 1]and[0, p_vowel - 1]. - The number of valid
i's ismax(0, min(p_vowel, p_k_minus_1) - p_k). Add this to the total answer. - All pointers only move forward, leading to a linear time complexity.
Walkthrough
We iterate through the string with a right pointer j from 0 to n-1. For each j, we maintain three left pointers: p_k, p_k_minus_1, and p_vowel. These pointers define the start of windows that satisfy certain conditions up to j.
p_k: The start of the shortest suffix ofword[0..j]with at mostkconsonants.p_k_minus_1: The start of the shortest suffix ofword[0..j]with at mostk-1consonants.p_vowel: The first indexisuch thatword[i..j]does not contain all 5 vowels.
For a fixed j, any starting index i in the range [p_k, p_k_minus_1 - 1] will result in a substring word[i..j] with exactly k consonants. Any starting index i < p_vowel will result in a substring with all 5 vowels. We need to count the number of indices i that satisfy both conditions. This corresponds to the length of the intersection of the valid ranges, which is max(0, min(p_vowel, p_k_minus_1) - p_k). By summing these counts for each j, we get the total number of beautiful substrings.
class Solution { private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public long beautifulSubstrings(String s, int k) { long ans = 0; int n = s.length(); int p_vowel = 0; int p_k = 0; int p_k_minus_1 = 0; int[] vowelCounts = new int[26]; int distinctVowels = 0; int consonants_k = 0; int consonants_k_minus_1 = 0; for (int j = 0; j < n; j++) { char char_j = s.charAt(j); if (isVowel(char_j)) { if (vowelCounts[char_j - 'a'] == 0) { distinctVowels++; } vowelCounts[char_j - 'a']++; } else { consonants_k++; consonants_k_minus_1++; } while (consonants_k > k) { if (!isVowel(s.charAt(p_k))) { consonants_k--; } p_k++; } while (consonants_k_minus_1 > k - 1) { if (!isVowel(s.charAt(p_k_minus_1))) { consonants_k_minus_1--; } p_k_minus_1++; } while (distinctVowels == 5) { char char_pv = s.charAt(p_vowel); if (isVowel(char_pv)) { vowelCounts[char_pv - 'a']--; if (vowelCounts[char_pv - 'a'] == 0) { distinctVowels--; } } p_vowel++; } ans += Math.max(0, Math.min(p_vowel, p_k_minus_1) - p_k); if (distinctVowels < 5 && p_vowel > 0) { char char_pv_prev = s.charAt(p_vowel - 1); if (isVowel(char_pv_prev)) { if (vowelCounts[char_pv_prev - 'a'] == 0) { distinctVowels++; } vowelCounts[char_pv_prev - 'a']++; } } } return ans; }}Complexity
Time
O(N), where N is the length of the string. Each of the four pointers (`j`, `p_vowel`, `p_k`, `p_k_minus_1`) traverses the string at most once.
Space
O(1), as the `vowelCounts` array has a fixed size of 26.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution that will pass for large inputs.
Cons
The logic is complex and involves careful state management of three interacting sliding windows.
Can be tricky to implement correctly without off-by-one errors.
Solutions
Solution
class Solution {public long countOfSubstrings(String word, int k) { return f(word, k) - f(word, k + 1); }private long f(String word, int k) { long ans = 0; int l = 0, x = 0; Map<Character, Integer> cnt = new HashMap<>(5); for (char c : word.toCharArray()) { if (vowel(c)) { cnt.merge(c, 1, Integer : : sum); } else { ++x; } while (x >= k && cnt.size() == 5) { char d = word.charAt(l++); if (vowel(d)) { if (cnt.merge(d, -1, Integer : : sum) == 0) { cnt.remove(d); } } else { --x; } } ans += l; } return ans; }private boolean vowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}class Solution {public: long long countOfSubstrings(string word, int k) { auto f = [&](int k) -> long long { long long ans = 0; int l = 0, x = 0; unordered_map<char, int> cnt; auto vowel = [&](char c) -> bool { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }; for (char c : word) { if (vowel(c)) { cnt[c]++; } else { ++x; } while (x >= k && cnt.size() == 5) { char d = word[l++]; if (vowel(d)) { if (--cnt[d] == 0) { cnt.erase(d); } } else { --x; } } ans += l; } return ans; }; return f(k) - f(k + 1); }};class Solution: def countOfSubstrings(self, word: str, k: int) -> int: def f(k: int) -> int: cnt = Counter() ans = l = x = 0 for c in word: if c in "aeiou": cnt[c] += 1 else: x += 1 while x >= k and len(cnt) == 5: d = word[l] if d in "aeiou": cnt[d] -= 1 if cnt[d] == 0: cnt . pop(d) else: x -= 1 l += 1 ans += l return ans return f(k) - f(k + 1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.