aboutsummaryrefslogtreecommitdiff
path: root/count_substr_rearr_cont_str2.py
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"))