↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-3298 统计重新排列后包含另一个字符串的子字符串数目 II #

Solution 1 #

重新排列后前缀是某个字符串, 用滑动窗口维护字符数量差值.

代码如下:

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        n = len(word1)
        if n < len(word2):
            return 0
        book = defaultdict(int)
        for ch in word2:
            book[ch] += 1
        less = len(book)
        ans = j = 0
        for i in range(n):
            while less > 0 and j < n:
                ch = word1[j]
                book[ch] -= 1
                if book[ch] == 0:
                    less -= 1
                j += 1
            if less == 0:
                ans += n - j + 1
            book[word1[i]] += 1
            if book[word1[i]] == 1:
                less += 1
        return ans