每日一题|3258. 统计满足 K 约束的子字符串数量 I|滑动窗口

1. 枚举

数据量不大，枚举直接拿下。

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        res = 0
        for i in range(len(s)):
            count = [0, 0]
            for j in range(i, len(s)):
                count[int(s[j])] += 1
                if count[0] > k and count[1] > k:
                    break
                res += 1
        return res

 2. 滑动窗口

枚举的时间开销是O(n * n)，很不美丽，所以需要找到一个不用全部遍历所有子字符串的方法。

如果一个字符串在一个区间内满足该条件，那么其中每一个子串都满足条件。

那么，如何一条不落下计入全部的子字符串呢？

答案是先固定一侧的指针，统计另一侧到这边一共有多少子串。

也就是说，我们对于每一个能够最大限度满足条件的区间求其一端到另一端的全部子串即可。这样一个需要消耗时间的遍历就变成了首尾索引的运算，节省了时间。

那么如何找到然后更新这个“最大长度”区间呢？

一侧动，另一侧不动。滑动窗口。

在出现右侧指针超过界限的时候，移动左侧指针，直到区间重新满足条件。

然后计算右侧指针不动的情况下的子串。

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        res = 0
        left = 0
        count = [0, 0]
        for i, c in enumerate(s):
            count[int(c) & 1] += 1
            while count[0] > k and count[1] > k:
                count[int(s[left]) & 1] -= 1
                left += 1
            res += i - left + 1
        return res