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

univerexplorer2025-01-102025-01-20

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

困难(滑动窗口)

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。

请你返回 word1 中合法 子字符串 的数目。

注意，这个问题中的内存限制比其他题目要小，所以你必须实现一个线性复杂度的解法。

示例 1：

输入：word1 = “bcca”, word2 = “abc”

输出：1

解释：

唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

示例 2：

输入：word1 = “abcabc”, word2 = “abc”

输出：10

解释：

除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：

输入：word1 = “abcabc”, word2 = “aaabc”

输出：0

代码一：

来自灵神（可通过leetcode3297）

超出时间限制 755 / 760 个通过的测试用例

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        if len(word1) < len(word2):
            return 0
        c1 = Counter()
        c2 = Counter(word2)
        ans = left = 0
        for i,s in enumerate(word1):
            c1[s] += 1
            while c1 >= c2:
                c1[word1[left]] -= 1
                left += 1
            ans += left
        return ans

思路：

word1 字符串从左到右依次存入，倘如存入的字符包含 word2 中的全部字符，说明此时满足条件。右边端点固定，左边端点开始右移，每次右移使移出的字符个数减一，直到不满足条件为止。此时 left 到右端点之间的字符串不满足条件，而 left-1 到右端点之间的字符串恰好满足条件，而左端点从 0 到 left-1 都满足，因此 while 循环一次一共有 left 个子字符串满足条件，以此类推直到右端点到头为止。

代码二：

优化代码，来自灵神

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        if len(word1) < len(word2):
            return 0
        c1 = Counter(word2)
        count = len(c1)
        ans = left = 0
        for s in word1:
            c1[s] -= 1
            if c1[s] == 0:
                count -= 1
            while count == 0:
                if c1[word1[left]] == 0:
                    count += 1
                c1[word1[left]] += 1
                left += 1
            ans += left
        return ans