blob: f1b57547063a8d0c777fb4c66bd1c4a57c1624a4 (
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
|
# 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"))
|