aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_substr_vowles_2.c42
-rw-r--r--count_substr_vowles_2.py57
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))