Scale Engineer

Count of Substrings Containing Every Vowel and K Consonants I

Med
#2935Time: 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.
Patterns
Sliding Window
Data structures
Hash TableString

Prompt

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

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 if c is a vowel.
  • Initialize a result counter count to 0.
  • Iterate through the string with an outer loop using index i from 0 to word.length() - 1. This i will be the starting index of our substrings.
  • For each i, start an inner loop with index j from i to word.length() - 1. This j will 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 j increments, update the consonant and vowel counts for the current character word.charAt(j).
  • After each update, check if the two conditions are met for the substring word[i..j]:
    1. The number of unique vowels is 5.
    2. 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 N were much larger. For the given constraints (N <= 250), it should pass, but it's not the most optimal solution.

Solutions

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.

← Previous

Previous problem

Next →

Next problem