Scale Engineer

Count of Substrings Containing Every Vowel and K Consonants II

Med
#2936Time: 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.
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 <= 2 * 105
  • word consists 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

  1. Generate all possible substrings of the word using two nested loops. The outer loop i iterates from 0 to n-1 (start of the substring), and the inner loop j iterates from i to n-1 (end of the substring).
  2. For each substring word[i..j], create a helper function to check if it meets the criteria.
  3. The helper function will iterate through the characters of the substring.
  4. Inside the helper function, use a frequency map or a set to count the number of distinct vowels and a separate counter for consonants.
  5. After iterating through the substring, check if the number of distinct vowels is exactly 5 and the number of consonants is exactly k.
  6. If both conditions are met, increment a global counter.
  7. 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.

Solutions

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';  }}

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