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

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "aeioubcdfghiju", k = 1

› Output: 0

💡 Note: No substring contains all vowels and exactly 1 consonant. Need at least 5 characters for all vowels, but with 1 consonant we'd need 6 total characters minimum.

Example 2 — All Vowels Present

$ Input: word = "aeiou", k = 0

› Output: 1

💡 Note: The substring "aeiou" contains all 5 vowels and exactly 0 consonants, so count is 1.

Example 3 — Multiple Valid Substrings

$ Input: word = "aeioubcd", k = 3

› Output: 1

💡 Note: The substring "aeioubcd" contains all vowels (a,e,i,o,u) and exactly 3 consonants (b,c,d).

Constraints

1 ≤ word.length ≤ 10⁵
word consists of only lowercase English letters
0 ≤ k ≤ word.length

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 20 a Amazon 15 f Meta 10

The key insight is to use the sliding window technique with the "at most k" approach. Calculate substrings with at most k consonants and all vowels, then subtract those with at most k-1 consonants to get exactly k consonants. Best approach is Sliding Window. Time: O(n), Space: O(1)

Common Approaches

✓ Brute Force - Check All Substrings

⏱️ Time: O(n³) Space: O(1)

Generate all possible substrings and for each one, count vowels and consonants to check if it meets our criteria. This approach examines every substring from every starting position.

Sliding Window with Hash Map

⏱️ Time: O(n) Space: O(1)

Transform the problem by calculating substrings with at most k consonants and all vowels, then subtract those with at most k-1 consonants and all vowels. This gives us exactly k consonants.

Brute Force - Check All Substrings — Algorithm Steps

Generate all possible substrings
For each substring, count vowels and consonants
Check if all 5 vowels are present and consonant count equals k
Count valid substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings

Count Characters

Count vowels and consonants in each

Validate

Check if criteria are met

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(char* word, int k) {
    int n = strlen(word);
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            bool vowelPresent[5] = {false}; // a,e,i,o,u
            int consonantCount = 0;
            int vowelCount = 0;
            
            for (int l = i; l <= j; l++) {
                char c = word[l];
                if (c == 'a' && !vowelPresent[0]) {
                    vowelPresent[0] = true;
                    vowelCount++;
                } else if (c == 'e' && !vowelPresent[1]) {
                    vowelPresent[1] = true;
                    vowelCount++;
                } else if (c == 'i' && !vowelPresent[2]) {
                    vowelPresent[2] = true;
                    vowelCount++;
                } else if (c == 'o' && !vowelPresent[3]) {
                    vowelPresent[3] = true;
                    vowelCount++;
                } else if (c == 'u' && !vowelPresent[4]) {
                    vowelPresent[4] = true;
                    vowelCount++;
                } else if (c != 'a' && c != 'e' && c != 'i' && c != 'o' && c != 'u') {
                    consonantCount++;
                }
            }
            
            if (vowelCount == 5 && consonantCount == k) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char word[1001];
    int k;
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(word, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: n² substrings, each taking O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to count characters, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler