blob: fd0be13df501dd6e6dfd06beaa1d26c812bdd01c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
// 3306. Count of Substrings Containing Every Vowel and K Consonants II
#include "leetcode.h"
/*
* you are given a string 'word' and a non-negative integer 'k'. return the
* total number of substrings of 'word' that contain every vowel at least once
* and exactly 'k' constants
*/
long long countOfSubstrings(char *word, int k) {
int freq[2][128] = {{0}};
freq[0]['a'] = freq[0]['e'] = freq[0]['i'] = freq[0]['o'] = freq[0]['u'] = 1;
long long ans = 0;
int curr = 0, cnt = 0, extra = 0, left = 0;
for (int right = 0; word[right]; right++) {
char r_char = word[right];
if (freq[0][r_char]) {
if (++freq[1][r_char] == 1)
cnt++;
} else
curr++;
while (curr > k) {
char l_char = word[left++];
if (freq[0][l_char]) {
if (--freq[1][l_char] == 0)
cnt--;
} else
curr--;
extra = 0;
}
if (curr == k && cnt == 5)
ans += (extra + 1);
}
return ans;
}
int main() {
char *w1 = "aeioqq", *w2 = "aeiou", *w3 = "ieaouqqieaouqq";
printf("%lld\n", countOfSubstrings(w1, 1)); // expect: 0
printf("%lld\n", countOfSubstrings(w2, 0)); // expect: 1
printf("%lld\n", countOfSubstrings(w3, 1)); // expect: 3
}
|