Welcome to Subscribe On Youtube

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

Solutions

Solution 1: Problem Transformation + Sliding Window

We can transform the problem into solving the following two subproblems:

1. Find the total number of substrings where each vowel appears at least once and contains at least $k$ consonants, denoted as $\mathit{\text{f}}(k)$;
2. Find the total number of substrings where each vowel appears at least once and contains at least $k+1$ consonants, denoted as $\mathit{\text{f}}(k+1)$.

Then the answer is $\mathit{\text{f}}(k)-\mathit{\text{f}}(k+1)$.

Therefore, we design a function $\mathit{\text{f}}(k)$ to count the total number of substrings where each vowel appears at least once and contains at least $k$ consonants.

We can use a hash table $\mathit{\text{cnt}}$ to count the occurrences of each vowel, a variable $\mathit{\text{ans}}$ to store the answer, a variable $\mathit{\text{l}}$ to record the left boundary of the sliding window, and a variable $\mathit{\text{x}}$ to record the number of consonants in the current window.

Traverse the string. If the current character is a vowel, add it to the hash table $\mathit{\text{cnt}}$; otherwise, increment $\mathit{\text{x}}$ by one. If $\mathit{\text{x}}\ge k$ and the size of the hash table $\mathit{\text{cnt}}$ is $5$, it means the current window meets the conditions. We then move the left boundary in a loop until the window no longer meets the conditions. At this point, all substrings ending at the right boundary $\mathit{\text{r}}$ and with the left boundary in the range $[0,..\mathit{\text{l}}-1]$ meet the conditions, totaling $\mathit{\text{l}}$ substrings. We add $\mathit{\text{l}}$ to the answer. Continue traversing the string until the end, and we get $\mathit{\text{f}}(k)$.

Finally, we return $\mathit{\text{f}}(k)-\mathit{\text{f}}(k+1)$.

The time complexity is $O(n)$, where $n$ is the length of the string $\mathit{\text{word}}$. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public long countOfSubstrings(String word, int k) {
          return f(word, k) - f(word, k + 1);
      }
  
      private long f(String word, int k) {
          long ans = 0;
          int l = 0, x = 0;
          Map<Character, Integer> cnt = new HashMap<>(5);
          for (char c : word.toCharArray()) {
              if (vowel(c)) {
                  cnt.merge(c, 1, Integer::sum);
              } else {
                  ++x;
              }
              while (x >= k && cnt.size() == 5) {
                  char d = word.charAt(l++);
                  if (vowel(d)) {
                      if (cnt.merge(d, -1, Integer::sum) == 0) {
                          cnt.remove(d);
                      }
                  } else {
                      --x;
                  }
              }
              ans += l;
          }
          return ans;
      }
  
      private boolean vowel(char c) {
          return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
      }
  }
  
  

• class Solution {
  public:
      long long countOfSubstrings(string word, int k) {
          auto f = [&](int k) -> long long {
              long long ans = 0;
              int l = 0, x = 0;
              unordered_map<char, int> cnt;
              auto vowel = [&](char c) -> bool {
                  return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
              };
              for (char c : word) {
                  if (vowel(c)) {
                      cnt[c]++;
                  } else {
                      ++x;
                  }
                  while (x >= k && cnt.size() == 5) {
                      char d = word[l++];
                      if (vowel(d)) {
                          if (--cnt[d] == 0) {
                              cnt.erase(d);
                          }
                      } else {
                          --x;
                      }
                  }
                  ans += l;
              }
              return ans;
          };
  
          return f(k) - f(k + 1);
      }
  };
  
  

• class Solution:
      def countOfSubstrings(self, word: str, k: int) -> int:
          def f(k: int) -> int:
              cnt = Counter()
              ans = l = x = 0
              for c in word:
                  if c in "aeiou":
                      cnt[c] += 1
                  else:
                      x += 1
                  while x >= k and len(cnt) == 5:
                      d = word[l]
                      if d in "aeiou":
                          cnt[d] -= 1
                          if cnt[d] == 0:
                              cnt.pop(d)
                      else:
                          x -= 1
                      l += 1
                  ans += l
              return ans
  
          return f(k) - f(k + 1)
  
  

• func countOfSubstrings(word string, k int) int64 {
  	f := func(k int) int64 {
  		var ans int64 = 0
  		l, x := 0, 0
  		cnt := make(map[rune]int)
  		vowel := func(c rune) bool {
  			return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
  		}
  		for _, c := range word {
  			if vowel(c) {
  				cnt[c]++
  			} else {
  				x++
  			}
  			for x >= k && len(cnt) == 5 {
  				d := rune(word[l])
  				l++
  				if vowel(d) {
  					cnt[d]--
  					if cnt[d] == 0 {
  						delete(cnt, d)
  					}
  				} else {
  					x--
  				}
  			}
  			ans += int64(l)
  		}
  		return ans
  	}
  
  	return f(k) - f(k+1)
  }
  
  

• function countOfSubstrings(word: string, k: number): number {
      const f = (k: number): number => {
          let ans = 0;
          let l = 0,
              x = 0;
          const cnt = new Map<string, number>();
  
          const vowel = (c: string): boolean => {
              return c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u';
          };
  
          for (const c of word) {
              if (vowel(c)) {
                  cnt.set(c, (cnt.get(c) || 0) + 1);
              } else {
                  x++;
              }
  
              while (x >= k && cnt.size === 5) {
                  const d = word[l++];
                  if (vowel(d)) {
                      cnt.set(d, cnt.get(d)! - 1);
                      if (cnt.get(d) === 0) {
                          cnt.delete(d);
                      }
                  } else {
                      x--;
                  }
              }
              ans += l;
          }
  
          return ans;
      };
  
      return f(k) - f(k + 1);
  }
  
  

• impl Solution {
      pub fn count_of_substrings(word: String, k: i32) -> i64 {
          fn f(word: &Vec<char>, k: i32) -> i64 {
              let mut ans = 0_i64;
              let mut l = 0;
              let mut x = 0;
              let mut cnt = std::collections::HashMap::new();
  
              let is_vowel = |c: char| matches!(c, 'a' | 'e' | 'i' | 'o' | 'u');
  
              for (r, &c) in word.iter().enumerate() {
                  if is_vowel(c) {
                      *cnt.entry(c).or_insert(0) += 1;
                  } else {
                      x += 1;
                  }
  
                  while x >= k && cnt.len() == 5 {
                      let d = word[l];
                      l += 1;
                      if is_vowel(d) {
                          let count = cnt.entry(d).or_insert(0);
                          *count -= 1;
                          if *count == 0 {
                              cnt.remove(&d);
                          }
                      } else {
                          x -= 1;
                      }
                  }
                  ans += l as i64;
              }
              ans
          }
  
          let chars: Vec<char> = word.chars().collect();
          f(&chars, k) - f(&chars, k + 1)
      }
  }
  
  

All Problems

All Solutions