aboutsummaryrefslogtreecommitdiff
path: root/count_substr_rearr_cont_str2.py
diff options
context:
space:
mode:
Diffstat (limited to 'count_substr_rearr_cont_str2.py')
-rw-r--r--count_substr_rearr_cont_str2.py37
1 files changed, 37 insertions, 0 deletions
diff --git a/count_substr_rearr_cont_str2.py b/count_substr_rearr_cont_str2.py
new file mode 100644
index 0000000..f1b5754
--- /dev/null
+++ b/count_substr_rearr_cont_str2.py
@@ -0,0 +1,37 @@
+# 3298. Count Substrings That Can Be Rearranged to Contain a String II
+from collections import Counter
+
+"""
+you are given two strings 'word1' and 'word2'. a string 'x' is called valiid
+if 'x' can be arranged to have 'word2' as a prefix. return the total number
+of valid strings of 'word1'. note that the memory limits in this problem are
+smaller than usual, so you must implement a solution with a linear runtime
+complexity.
+"""
+
+
+class Solution(object):
+ def validSubstringCount(self, word1, word2):
+ """
+ :type word1: str
+ :type word2: str
+ :rtype: int
+ """
+ cnt = Counter(word2)
+ k, ans, i = len(word2), 0, 0
+ for j, c in enumerate(word1):
+ if cnt[c] > 0:
+ k -= 1
+ cnt[c] -= 1
+ while k == 0 and cnt[word1[i]] < 0:
+ cnt[word1[i]] += 1
+ i += 1
+ ans += 0 if k else i + 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.validSubstringCount(word1="bcca", word2="abc"))
+ print(obj.validSubstringCount(word1="abcabc", word2="abc"))
+ print(obj.validSubstringCount(word1="abcabc", word2="aaabc"))