滑动窗口字符计数的优化：增加维护聚合信息应对高频查询

摘要: 以滑动窗口的方式统计满足条件的子串数目，聚合信息的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在上一篇文章 滑动窗口 | 满足条件的子串数目 中，我们解决了字符串上字符计数满足一定条件的子串的数目的问题。算法的核心是滑动窗口，过程中维护窗口内的字符计数。

不过上一篇文章实现的比较粗糙，窗口边界每次推进，都要判断窗内的子串是否满足条件，判断的过程需要对比一次字符计数，一次对比需要将 26 个字符都过一遍。这样时间复杂度虽然是 $O(N)$，但常数至少是 26。当数据量变大时，就需要优化了，本文我们来看一下这个优化。

本文的题目与上一篇文章的描述一样，仅仅是数据量变为了原来的十倍。力扣平台标的难度也从中等变为了困难。优化的思想很简单，就是在维护的字符计数的基础上增加聚合信息，使得“判断窗内子串是否满足条件”这一高频查询的效率提升。最终时间复杂度中的常数 26 可以优化为 1。

题目

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

给你两个字符串 word1 和 word2 。

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

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

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

解释：

1 <= word1.length <= 1e6
1 <= word2.length <= 1e4
word1 和 word2 都只包含小写英文字母。

示例 1：
输入：word1 = “bcca”, word2 = “abc”
输出：1
解释：
唯一合法的子字符串是 “bcca” ，可以重新排列得到 “abcc” ，”abc” 是它的前缀。

示例 2：
输入：word1 = “abcabc”, word2 = “abc”
输出：10
解释：
除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：
输入：word1 = “abcabc”, word2 = “aaabc”
输出：0

题解

算法: 滑动窗口 + 聚合信息

算法的主框架与 滑动窗口 | 满足条件的子串数目 完全一样，只是滑动窗口内维护的信息做一些调整，使得滑动窗口过程中比较高频的查询操作可以更高效。

由于窗口边界推进一次，只会对一个字符产生变化，如果是左边界推进，则窗口内某个字符的计数 -1，如果右边界推进，则窗口内某个字符的计数 -1。因此由窗口边界的推进造成窗口内子串的合法性的变化，仅取决于边界这个字符，这样判断合法性的时候理应不需要把 26 个字符都检查一遍。

当前窗口如果不合法，则右边界 r 推进一步，如果 word1[r] 对应的字符计数 cnt[word1[r]] 在 +1 之前不合法，而 +1 之后合法了，那么此时窗口内子串会不会因此从不合法变合法呢，关键在于窗口内尚未满足要求的字符个数是多少，对未满足要求的具体字符并不关心，因此考虑对窗口内的字符计数维护一个聚合信息，即窗口内尚未满足要求的字符的个数，记为 s。

s 在初始时为 word2 的字符计数 cnt2 中大于 0 的字符个数，当 r 推进使得字符 word1[r] 从不合法变合法，更新 s -= 1，然后通过 s 是否为零就可以判断窗口内的子串是否已经合法，而无需将 26 个字符都走一遍。这是引入聚合信息后带来的优化。

当前窗口如果合法，则左边界 l 推进一步，word1[l] 的字符计数 -1，如果因此造成了字符 word1[l] 从合法变成了不合法，更新 s+=1 即可。

代码 (Python)

from collections import Counter

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        cnt2 = Counter(word2)
        s = len(cnt2)
        l = 0
        r = -1
        cnt = Counter()
        ans = 0
        while l < n1 and r < n1:
            while s > 0:
                r += 1
                if r >= n1:
                    break
                cnt[word1[r]] += 1
                # 维护增加的聚合信息 s
                if cnt2[word1[r]] - cnt[word1[r]] == 0:
                    s -= 1

            if r < n1:
                ans += n1 - r
            cnt[word1[l]] -= 1
            # 维护增加的聚合信息 s
            if cnt2[word1[l]] - cnt[word1[l]] > 0:
                s += 1
            l += 1
        return ans

总结

在维护滑动窗口时，一个最常见的查询操作是判断窗口是否合法，这是一个高频查询，为了优化这个查询的效率，需要灵活使用各种数据结构来维护窗口内的信息，本文的题目比较简单，通过增加一个聚合信息即可解决，在更复杂的场景需要一些数据结构，比如之前我们提到过，数据压缩的 LZ77 方法，在优化过程中使用了后缀树来提高查询效率。

---