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

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        if len(word2)>len(word1):
            return 0
        #数组记录字符出现次数
        cnt=[0]*26
        for c in word2:
            cnt[ord(c)-ord('a')]+=1
        #计算 “cnt” 中大于 0 的元素的数量，并将这个数量存储在 “need” 变量中
        need=sum(1 for count in cnt if count>0)
        window_count=[0]*26
        count_met=0
        total=0
        left=0
        #先同样方法记录word1出现的字符
        for right,c in enumerate(word1):
            idx=ord(c)-ord('a')
            window_count[idx]+=1
            if window_count[idx]==cnt[idx]:
                count_met+=1
            while count_met==need:
                total+=len(word1)-right
                char_left=word1[left]
                idx_left=ord(char_left)-ord('a')
                window_count[idx_left]-=1

                if window_count[idx_left]<cnt[idx_left]:
                    count_met-=1
                left+=1
        return total

        

原文地址：https://blog.csdn.net/m0_73629042/article/details/142436898

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！