滑动窗口 | 满足条件的子串数目

字数统计: 1.2k字   |   阅读时长: 4分

摘要: 以滑动窗口的方式统计满足条件的子串数目

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

各位好，今天我们来看一个在字符串上通过滑动窗口进行子串统计的问题。在滑动窗口推进的过程中，维护字符计数进行一些统计是一大类问题，参考此前的汇总文章 双指针和滑动窗口题目汇总。

最早提出滑动窗口这个概念是在数据压缩的论文中，Jacob Ziv 和 Abraham Lempel 在 1977 和 1978 年发表了两篇基于自适应词典进行数据压缩的里程碑式论文，两篇论文构建词典的路线不一样。其中 1977 年提出的方法以及后续的各种变种称为 LZ77 方法，该方法通过在已处理的数据中查找与当前数据相匹配的最长子串来实现压缩，编码器通过一个滑动窗口来查看输入序列，这也是首次提出滑动窗口的概念。

此后滑动窗口就成为了字符串（包括数组）上的一大类算法，Maxime Crochemore 在 2007 年出版的《Algorithms on Strings》中的第三章专门介绍了字符串上的滑动窗口，可以参考：

这本书讲的比较深入，需要研究生级别的理论基础，以后有时间可以跟大家一起啃一啃，感兴趣的朋友可以通过以下链接下载本书：

• 《Algorithms on Strins》

LZ77 算法本身也是现在我们在谈字符串算法时的一个经典算法，很多讲字符串的书上都有提到，包括后续对 LZ77 算法的查找过程进行优化时还能引出后缀树这一重要数据结构。

题目

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

给你两个字符串 word1 和 word2 。

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

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

解释：

1
2
3

1 <= word1.length <= 1e5
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

题解

算法: 滑动窗口

记 word1 的长度为 n1，word2 的长度为 n2。记 word2 的字符计数为 cnt2，即 cnt2[c] 表示 word2 中字符 c 的数目。

对于 word1[l..r] 这一段子串，记其字符计数为 cnt，如果 cnt 中各个字符的数目均不小于 cnt2，则该段子串合法。

当 word1[l..r] 合法时，word1[l..x]，当 r <= x < n1 时显然均合法。基于这一点我们就有了以下基于滑动窗口的思路。

从小到大依次枚举左端点 l=0,1,...,n-1，当固定 l 时，向右推进右端点 r，直至 word1[l..r] 刚好满足要求，记此时的右端点为 $r_{l}$。这样以 l 为左端点的子串，满足要求的右端点为 $r_{l},r_{l}+1,…,n_{1}-1$，共 $n_{1}-r_{l}$ 个。

由于 $r_{l}$ 是以 l 为左端点的子串中，使得 word1[l..r] 满足要求的最小的 r，也就是说 word1[l..r-1] 是不满足要求的。因此进入下一轮后，以 l+1 为左端点时，word1[l+1..r-1] 肯定也不满足要求，因此 $r_{l+1} \geq r_{l}$，这样 r 就从上一轮的位置开始推进即可，无需往回走。

最终答案为 $\sum\limits_{l=0}\limits^{n_{1}-1}(n_{1} - r_{l})$。

由于 l 从左到右走一趟，r 也是从左到右走一趟，总时间复杂度为 $O(n)$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from collections import Counter

def contain(cnt, cnt2):
    
    return all(cnt[c] >= cnt2[c] for c in cnt2)

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        cnt2 = Counter(word2)
        l = 0
        r = -1
        cnt = Counter()
        ans = 0
        while l < n1 and r < n1:
            while not contain(cnt, cnt2):
                r += 1
                if r >= n1:
                    break
                cnt[word1[r]] += 1
            if r < n1:
                ans += n1 - r
            cnt[word1[l]] -= 1
            l += 1
        return ans