Understand Count of Substrings Containing Every Vowel and K Consonants II Problem

Problem Name: Count of Substrings Containing Every Vowel and K Consonants II
Problem Description:

Count of Substrings Containing Every Vowel and K Consonants II

Problem Statement

Given a string word and a non-negative integer k, return the total number of substrings of word that satisfy both of the following conditions:

  • Contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once.
  • Contain exactly k consonants.

Explanation

The task is to count all contiguous substrings of the input string word that:

  • Include all the vowels: a, e, i, o, and u.
  • Have exactly k consonants (letters that are not vowels).

Constraints

  • 5 <= word.length <= 2 * 10^5
  • word consists only of lowercase English letters.
  • 0 <= k <= word.length - 5

Examples

Example 1

  • Input: word = "cuaeio", k = 1
  • Explanation:
    The only valid substring is "cuaeio". It contains all vowels (u, a, e, i, o) and exactly 1 consonant (c).
  • Output: 1

Example 2

  • Input: word = "aeioubt", k = 2
  • Explanation:
    The substring "aeioubt" has all vowels and exactly 2 consonants (b and t). No other substring meets the criteria.
  • Output: 1

Example 3

  • Input: word = "abaeiou", k = 1
  • Explanation:
    There are two valid substrings:
    • "baeiou" (from index 1 to 6) contains vowels (a, e, i, o, u) and 1 consonant (b).
    • "abaeiou" (from index 0 to 6) also contains all vowels and exactly 1 consonant (b).
  • Output: 2

Constraints

  • 5<=word.length<=2∗1055 <= word.length <= 2 * 10^5
  • word consists only of lowercase English letters.
  • 0<=k<=word.length−5 0 <= k <= word.length - 5
Category:
  • Heaps & Hashing
  • Leetcode Problem of the Day
Programming Language:
  • Java
Reference Link:

https://leetcode.com/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii/description/

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
Main Function is not defined.
Helper Function:
INPUT: word = "abaeiou", k = 1
OUTPUT: 2
public static long countOfSubstrings(String word, int k) {
  int[][] frequencies = new int[2][128];
  frequencies[0]['a'] = 1;
frequencies[0]['e'] = 1;
 frequencies[0]['i'] = 1;
frequencies[0]['o'] = 1;
frequencies[0]['u'] = 1;
long response = 0;
int currentK = 0;
int vowels = 0;
int extraLeft = 0;
for (int right = 0, left = 0; right < word.length(); right++) {
char rightChar = word.charAt(right);
 if (frequencies[0][rightChar] == 1) {
if (++frequencies[1][rightChar] == 1){
vowels++;
}//If End
}//If End
else{
 currentK++;
}//Else End
 while (currentK > k) {
char leftChar = word.charAt(left);
if (frequencies[0][leftChar] == 1) {
if (--frequencies[1][leftChar] == 0){
vowels--;
}//If End
}//If End
else {
currentK--;
}//Else End
left++;
extraLeft = 0;
}//Loop End
 while (vowels == 5 && currentK == k && left < right && frequencies[0][word.charAt(left)] == 1 && frequencies[1][word.charAt(left)] > 1) {
extraLeft++;
frequencies[1][word.charAt(left)]--;
left++;
}//Loop End
if (currentK == k && vowels == 5) {
 response += (1 + extraLeft);
}//If End
}//Loop End
 return response;
}//function end
Utility Functions and Global variables:
Utility Function is not required.
Privacy Policy | About