Count of Substrings Containing Every Vowel and K Consonants II

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

Understanding the Visualization

Input

String with vowels and consonants, target consonant count

Process

Use sliding window to find valid substrings

Output

Count of substrings with all vowels and exactly k consonants

Key Takeaway

🎯 Key Insight: Transform exact count to difference of at-most counts using sliding window

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

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring to see if it contains all vowels and exactly k consonants
Sliding Window with Hash Map	O(n)	O(1)	Use two sliding windows to count substrings with at most k consonants minus at most k-1 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler