Count of Substrings Containing Every Vowel and K Consonants I
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 <= 250wordconsists only of lowercase English letters.0 <= k <= word.length - 5
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible substrings of the given word. For each starting position, it expands the substring one character at a time to the right, keeping a running count of the number of consonants and the set of unique vowels encountered. This avoids re-calculating these counts for every single substring from scratch.
Algorithm
- Create a helper function
isVowel(char c)that returns true ifcis a vowel. - Initialize a result counter
countto 0. - Iterate through the string with an outer loop using index
ifrom 0 toword.length() - 1. Thisiwill be the starting index of our substrings. - For each
i, start an inner loop with indexjfromitoword.length() - 1. Thisjwill be the ending index. - Inside the inner loop, for each substring
word[i..j], maintain a count of consonants and a way to track unique vowels (e.g., a set or a frequency map). - As
jincrements, update the consonant and vowel counts for the current characterword.charAt(j). - After each update, check if the two conditions are met for the substring
word[i..j]:- The number of unique vowels is 5.
- The number of consonants is exactly
k.
- If both conditions are true, increment the
count. - After the loops complete, return the total
count.
Walkthrough
The most straightforward way to solve this problem is to check every possible substring. We can use two nested loops to define the start and end points of a substring. The outer loop fixes the starting index i, and the inner loop iterates the ending index j from i to the end of the string.
For each starting index i, we initialize a consonant counter and a data structure to keep track of the unique vowels seen so far (a boolean array or a hash set works well). As we extend the substring by moving the end pointer j, we update these counts based on the character word.charAt(j). After adding each new character, we check if the current substring word[i..j] satisfies the problem's criteria: containing all five vowels and exactly k consonants. If it does, we increment our result counter.
This method is easy to understand because it directly translates the problem statement into code, but its performance is not optimal due to the nested loops.
class Solution { private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } public int countSubstrings(String word, int k) { int n = word.length(); int result = 0; for (int i = 0; i < n; i++) { int consonants = 0; // Using a boolean array for vowels 'a','e','i','o','u' boolean[] vowelsFound = new boolean[5]; int distinctVowels = 0; for (int j = i; j < n; j++) { char c = word.charAt(j); if (isVowel(c)) { int vowelIndex = "aeiou".indexOf(c); if (!vowelsFound[vowelIndex]) { vowelsFound[vowelIndex] = true; distinctVowels++; } } else { consonants++; } if (distinctVowels == 5 && consonants == k) { result++; } } } return result; }}Complexity
Time
O(N^2), where N is the length of `word`. The two nested loops iterate through approximately N^2/2 substrings, and the work inside the inner loop is O(1).
Space
O(1), as the space used for tracking vowels (e.g., a boolean array of size 5 or a set of max size 5) and the consonant count is constant regardless of the input string size.
Trade-offs
Pros
Simple to conceptualize and implement.
It is a correct, brute-force solution that directly models the problem statement.
Cons
The time complexity is quadratic, which might be too slow if the input string length
Nwere much larger. For the given constraints (N <= 250), it should pass, but it's not the most optimal solution.
Solutions
Solution
class Solution {public int countOfSubstrings(String word, int k) { return f(word, k) - f(word, k + 1); }private int f(String word, int k) { int 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'; }}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.