aboutsummaryrefslogtreecommitdiff
path: root/count_substr_vowles_2.py
diff options
context:
space:
mode:
Diffstat (limited to 'count_substr_vowles_2.py')
-rw-r--r--count_substr_vowles_2.py57
1 files changed, 57 insertions, 0 deletions
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))