diff options
-rw-r--r-- | count_substr_vowles_2.c | 42 | ||||
-rw-r--r-- | count_substr_vowles_2.py | 57 |
2 files changed, 99 insertions, 0 deletions
diff --git a/count_substr_vowles_2.c b/count_substr_vowles_2.c new file mode 100644 index 0000000..fd0be13 --- /dev/null +++ b/count_substr_vowles_2.c @@ -0,0 +1,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 +} diff --git a/count_substr_vowles_2.py b/count_substr_vowles_2.py new file mode 100644 index 0000000..c230ba8 --- /dev/null +++ b/count_substr_vowles_2.py @@ -0,0 +1,57 @@ +# 3306. 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 at least once +and exactly 'k' constants +""" + + +class Solution(object): + def countOfSubstrings(self, word, k): + """ + :type word: str + :type k: int + :rtype: int + """ + freq = [{}, {}] + for v in "aeiou": + freq[0][v] = 1 + ans, curr, cnt, extra, left = 0, 0, 0, 0, 0 + for right, r_char in enumerate(word): + if r_char in freq[0]: + freq[1][r_char] = freq[1].get(r_char, 0) + 1 + if freq[1][r_char] == 1: + cnt += 1 + else: + curr += 1 + while curr > k: + l_char = word[left] + if l_char in freq[0]: + freq[1][l_char] -= 1 + if freq[1][l_char] == 0: + cnt -= 1 + else: + curr -= 1 + left += 1 + extra = 0 + while ( + cnt == 5 + and curr == k + and left < right + and word[left] in freq[0] + and freq[1][word[left]] > 1 + ): + extra += 1 + freq[1][word[left]] -= 1 + left += 1 + if curr == k and cnt == 5: + ans += extra + 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countOfSubstrings(word="aeioqq", k=1)) + print(obj.countOfSubstrings(word="aeiou", k=0)) + print(obj.countOfSubstrings(word="ieaouqqieaouqq", k=1)) |