2025-03-10 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 10

Description

Count of Substrings Containing Every Vowel and K Consonants II

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.

 

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

Solution

inline bool isVowel(char c) {
  return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
class Solution {
  long long geK(string word, int k) {
    long long result = 0;
    int start = 0;
    unordered_map<char, int> vowelCount;
    int consonants = 0;

    for(int end = 0; end < word.length(); ++end) {
      char c = word[end];
      if(isVowel(c)) {
        vowelCount[c] += 1;
      } else {
        consonants += 1;
      }

      while(vowelCount.size() == 5 && consonants >= k) {
        result += word.length() - end;
        char cs = word[start];
        if(isVowel(cs)) {
          vowelCount[cs] -= 1;
          if(!vowelCount[cs]) vowelCount.erase(cs);
        } else {
          consonants -= 1;
        }
        start += 1;
      }
    }
    return result;
  }
public:
  long long countOfSubstrings(string word, int k) {
    return geK(word, k) - geK(word, k + 1);
  }
};

// Accepted
// 768/768 cases passed (196 ms)
// Your runtime beats 51.12 % of cpp submissions
// Your memory usage beats 55.62 % of cpp submissions (48.7 MB)
Algorithm