LC3297. 统计重新排列后包含另一个字符串的子字符串数目 I

题目链接：

题解

• [[LC3298. 统计重新排列后包含另一个字符串的子字符串数目 II]] 弱化版本，只有可以参考那一道写出 O(n) 复杂度的解法。

参考代码

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        
        ans = 0
        b_cnt = defaultdict(int)
        for s in word2:
            b_cnt[s] += 1
        n = len(word1)
        a_cnt = defaultdict(int)
        tmp = 0
        st = 0
        for i in range(0, n):
            
            if tmp == len(word2):
                 break
            
            st = i
            a_cnt[word1[i]] += 1

            if a_cnt[word1[i]] == b_cnt[word1[i]]:
                tmp += b_cnt[word1[i]]
            
        if tmp != len(word2):
            return 0
        ans = 0

        tt = 0
        while  a_cnt[word1[tt]] - 1 >= b_cnt[word1[tt]]:
            a_cnt[word1[tt]] -= 1
            tt += 1
        
        ans += tt + 1

        for i in range(st+1, n):
            # print(i, ans, tt)

            a_cnt[word1[i]] += 1
            while a_cnt[word1[tt]] - 1 >= b_cnt[word1[tt]]:
                a_cnt[word1[tt]] -= 1
                tt += 1
            # a_cnt[word1[i]] += 1
            ans += tt + 1
        return ans