Count of Substrings Containing Every Vowel and K Consonants I

Medium
1368.

Count of Substrings Containing Every Vowel and K Consonants I

Count of Substrings Containing Every Vowel and K Consonants I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

You are given a string word of lowercase English letters and a non-negative integer k.

Return the number of substrings of word that contain every vowel (a, e, i, o and u) at least once and exactly k consonants. Substrings at different positions count separately.

Example 1

Input
word = "uoieax", k = 1
Output
1
Explanation
Only the whole word has all five vowels and one consonant; `"uoiea"` has all vowels but no consonant.

Example 2

Input
word = "aeiouaeiou", k = 0
Output
21
Explanation
Every window of length 5 or more holds all five vowels and no consonant: 6 + 5 + 4 + 3 + 2 + 1.

Example 3

Input
word = "aeixou", k = 0
Output
0
Explanation
Any substring with all five vowels must include the `x`.

Constraints

  • 5 <= word.length <= 250
  • word consists only of lowercase English letters.
  • 0 <= k <= word.length - 5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var countOfSubstrings = function(word, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count of Substrings Containing Every Vowel and K Consonants I Solution

Count of Substrings Containing Every Vowel and K Consonants I solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count of Substrings Containing Every Vowel and K Consonants I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Sliding Window
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string word of lowercase English letters and a non-negative integer k.

Return the number of substrings of word that contain every vowel (a, e, i, o and u) at least once and exactly k consonants. Substrings at different positions count separately.

Example 1

Input: word = "uoieax", k = 1
Output: 1
Explanation: Only the whole word has all five vowels and one consonant; `"uoiea"` has all vowels but no consonant.

Example 2

Input: word = "aeiouaeiou", k = 0
Output: 21
Explanation: Every window of length 5 or more holds all five vowels and no consonant: 6 + 5 + 4 + 3 + 2 + 1.

Example 3

Input: word = "aeixou", k = 0
Output: 0
Explanation: Any substring with all five vowels must include the `x`.

Constraints

  • 5 <= word.length <= 250
  • word consists only of lowercase English letters.
  • 0 <= k <= word.length - 5

Hints for Count of Substrings Containing Every Vowel and K Consonants I

  1. Hint 1

    "Exactly k consonants" is awkward for a sliding window, but "at least m consonants" is monotone: extending a qualifying substring keeps it qualifying.

  2. Hint 2

    So count atLeast(k) - atLeast(k + 1), where atLeast(m) counts substrings with all five vowels and at least m consonants.

  3. Hint 3

    For atLeast(m): slide right; while the window has all five vowels and at least m consonants, drop word[left] and advance left. Then every start before left works for this right — add left.

How to solve Count of Substrings Containing Every Vowel and K Consonants I

Turn the exact count into a difference of two monotone counts. "All vowels and at least m consonants" survives extension, so for each right end the valid starts are a prefix, which a sliding window measures.

Approach

  1. Define atLeast(m): keep vowel counts, the number of distinct vowels present, a consonant count, left = 0 and a total.
  2. For each right, add word[right] (a vowel's count, or one more consonant).
  3. While the window has all five vowels and at least m consonants, remove word[left] and advance left.
  4. Add left to the total: the starts 0 .. left-1 all give valid substrings ending at right.
  5. Answer atLeast(k) - atLeast(k + 1).

Why it works

A substring with exactly k consonants and all vowels is counted by atLeast(k) but not by atLeast(k + 1), and every substring with more consonants is counted by both — so the difference is exactly the requested count. Inside atLeast(m), the shrink loop stops at the first start that fails; every earlier start gives a superset of a valid window and is valid, and since extending to the right keeps validity, left never moves back.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • A plain window for "exactly k" is not monotone: adding a vowel never changes the consonant count, so the valid starts for one end are not a contiguous prefix.
  • Track distinct vowels: "aaaaa" has five vowels but only one distinct one.
  • With n <= 250 an O(n²) scan with early break is also fine; the sliding-window version is what the larger variant (n up to 2·10^5) needs.

Reference solution

Python

def countOfSubstrings(word: str, k: int) -> int:
    def at_least(m: int) -> int:
        cnt = {}
        cons = 0
        left = 0
        total = 0
        for ch in word:
            if ch in "aeiou":
                cnt[ch] = cnt.get(ch, 0) + 1
            else:
                cons += 1
            while len(cnt) == 5 and cons >= m:
                d = word[left]
                if d in "aeiou":
                    cnt[d] -= 1
                    if cnt[d] == 0:
                        del cnt[d]
                else:
                    cons -= 1
                left += 1
            total += left
        return total

    return at_least(k) - at_least(k + 1)

Java

static boolean isVowel3305(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

static int atLeast3305(String word, int m) {
    int[] cnt = new int[26];
    int distinct = 0, cons = 0, left = 0, total = 0;
    for (int right = 0; right < word.length(); right++) {
        char c = word.charAt(right);
        if (isVowel3305(c)) { if (cnt[c - 'a']++ == 0) distinct++; } else cons++;
        while (distinct == 5 && cons >= m) {
            char d = word.charAt(left);
            if (isVowel3305(d)) { if (--cnt[d - 'a'] == 0) distinct--; } else cons--;
            left++;
        }
        total += left;
    }
    return total;
}

public static int countOfSubstrings(String word, int k) {
    return atLeast3305(word, k) - atLeast3305(word, k + 1);
}

C++

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

int atLeast3305(const string& word, int m) {
    int cnt[26] = {0};
    int distinct = 0, cons = 0, left = 0, total = 0;
    for (int right = 0; right < (int) word.size(); right++) {
        char c = word[right];
        if (isVowel3305(c)) { if (cnt[c - 'a']++ == 0) distinct++; } else cons++;
        while (distinct == 5 && cons >= m) {
            char d = word[left];
            if (isVowel3305(d)) { if (--cnt[d - 'a'] == 0) distinct--; } else cons--;
            left++;
        }
        total += left;
    }
    return total;
}

int countOfSubstrings(string word, int k) {
    return atLeast3305(word, k) - atLeast3305(word, k + 1);
}

JavaScript

var countOfSubstrings = function(word, k) {
    var isVowel = function(c) {
        return c === "a" || c === "e" || c === "i" || c === "o" || c === "u";
    };
    var atLeast = function(m) {
        var cnt = { a: 0, e: 0, i: 0, o: 0, u: 0 };
        var distinct = 0, cons = 0, left = 0, total = 0;
        for (var right = 0; right < word.length; right++) {
            var c = word[right];
            if (isVowel(c)) { if (cnt[c]++ === 0) distinct++; } else cons++;
            while (distinct === 5 && cons >= m) {
                var d = word[left];
                if (isVowel(d)) { if (--cnt[d] === 0) distinct--; } else cons--;
                left++;
            }
            total += left;
        }
        return total;
    };
    return atLeast(k) - atLeast(k + 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets