3306. Count of Substrings Containing Every Vowel and K Consonants II

Description

You are given a string word and a non-negative integer k.

Return the total number of of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

 

Example 1:

Input: word = "aeioqq", k = 1

Output: 0

Explanation:

There is no substring with every vowel.

Example 2:

Input: word = "aeiou", k = 0

Output: 1

Explanation:

The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".

Example 3:

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

• word[0..5], which is "ieaouq".
• word[6..11], which is "qieaou".
• word[7..12], which is "ieaouq".

 

Constraints:

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

 

Solutions

Solution: Sliding Window

• Time complexity: O(n+n -> n)
• Space complexity: O(5 -> 1)

 

JavaScript

/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
const countOfSubstrings = function (word, k) {
  const n = word.length;
  const vowels = ['a', 'e', 'i', 'o', 'u'];

  const isVowel = letter => vowels.includes(letter);

  const atMost = consonants => {
    const vowelMap = new Map();
    let left = 0;
    let consonantCount = 0;
    let result = 0;

    for (let index = 0; index < n; index++) {
      const letter = word[index];

      if (isVowel(letter)) {
        const count = vowelMap.get(letter) ?? 0;

        vowelMap.set(letter, count + 1);
      } else {
        consonantCount += 1;
      }

      while (vowelMap.size === vowels.length && consonantCount > consonants) {
        const current = word[left];

        if (isVowel(current)) {
          const count = vowelMap.get(current);

          count === 1 ? vowelMap.delete(current) : vowelMap.set(current, count - 1);
        } else {
          consonantCount -= 1;
        }

        left += 1;
      }

      result += index - left + 1;
    }

    return result;
  };

  return atMost(k) - atMost(k - 1);
};