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

题目链接：3298. 统计重新排列后包含另一个字符串的子字符串数目 II - 力扣（LeetCode）

题解

• [[LC3297. 统计重新排列后包含另一个字符串的子字符串数目 I]] 强化版本

• 双指针，word1 (tt, i) 对应的一个满足题目要求，包含所有 word2 中字母的区间。每一次更新 i 往后移动一位，然后考虑 tt 能不能移动，每次对答案的贡献是 tt+1

参考代码

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