Count of Substrings Containing Every Vowel and K Consonants I

Count of Substrings Containing Every Vowel and K Consonants I - 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 = "aeioqq", k = 1

› Output: 0

💡 Note: No substring contains all vowels (a,e,i,o,u) and exactly 1 consonant. Missing vowel 'u'.

Example 2 — Valid Case

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

› Output: 1

💡 Note: The substring "aeiou" contains all vowels and exactly 0 consonants.

Example 3 — Multiple Valid

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

› Output: 1

💡 Note: The substring "aeiouc" contains all vowels (a,e,i,o,u) and exactly 1 consonant (c).

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String word and integer k

Process

Find all substrings with all vowels and exactly k consonants

Output

Count of valid substrings

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently track character counts and avoid redundant substring generation

Asked in

G Google 15 M Microsoft 12 a Amazon 10

The key insight is to use sliding window technique to efficiently track vowel completeness and consonant count. Best approach is sliding window with early termination. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check every possible substring and count vowels and consonants
Sliding Window	O(n²)	O(1)	Use expanding window to track vowels and consonants efficiently

Brute Force — Algorithm Steps

Generate all possible substrings
For each substring, count vowels and consonants
Check if all vowels present and consonants = k

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 is met

Code -

solution.c — C

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

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int solution(char* word, int k) {
    int count = 0;
    int n = strlen(word);
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            bool vowelsSeen[5] = {false};
            int consonantCount = 0;
            
            for (int idx = i; idx <= j; idx++) {
                char c = word[idx];
                if (isVowel(c)) {
                    if (c == 'a') vowelsSeen[0] = true;
                    else if (c == 'e') vowelsSeen[1] = true;
                    else if (c == 'i') vowelsSeen[2] = true;
                    else if (c == 'o') vowelsSeen[3] = true;
                    else if (c == 'u') vowelsSeen[4] = true;
                } else {
                    consonantCount++;
                }
            }
            
            int vowelCount = 0;
            for (int v = 0; v < 5; v++) {
                if (vowelsSeen[v]) vowelCount++;
            }
            
            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³)

Nested loops to generate substrings O(n²) and checking each substring O(n)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant space for counters

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

340 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 — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler