统计满足 K 约束的子字符串数量-LeetCode

3258. 统计满足 K 约束的子字符串数量

🎯 问题描述（来源于LeetCode）

描述：
给定一个二进制字符串 s 和一个整数 k。
如果一个子串满足以下条件之一，则称该子串符合 K 约束：

• 子串中 0 的个数不超过 k；
• 子串中 1 的个数不超过 k。

请返回符合 K 约束的子串总数。

说明：

• 子串是连续的。
• 字符串长度 1 <= s.length <= 50（对于本解法，滑动窗口可处理更大规模）。

示例：

• 示例 1：

输入: s = "10101", k = 1
输出: 12
解释: 所有 15 个子串中，只有 "101", "0101", "1010", "10101" 不符合（因为 0 和 1 的个数都 > 1），其余 12 个符合。

• 示例 2：

输入: s = "1010101", k = 2
输出: 25

💻 解题思路

思路：滑动窗口（双指针）

算法步骤

1. 将字符串转为数字列表，便于操作（ch = [int(c) for c in s]）。
2. 初始化左指针 left = 0，计数器 count = {0:0, 1:0}，答案 ans = 0。
3. 遍历右指针 right，将当前字符 ch[right] 加入窗口计数。
4. 当窗口内 0 的个数和 1 的个数都大于 k 时，说明该窗口（以及以 right 为右端点且左端点更靠右的窗口）不满足条件，需要移动左指针缩小窗口，直到至少一类字符的个数 ≤ k。
   • 将左指针指向的字符从计数中减去，左指针右移。
5. 此时，以 right 为右端点且左端点从 left 到 right 的所有子串都满足条件，数量为 right - left + 1，累加到 ans。
6. 返回 ans。

代码实现

from typing import List

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        ch = [int(c) for c in s]
        count = {0: 0, 1: 0}
        left = 0
        ans = 0
        for right, st in enumerate(ch):
            count[st] += 1
            while count[0] > k and count[1] > k:
                count[ch[left]] -= 1
                left += 1
            ans += right - left + 1
        return ans

📊 性能分析

• 时间复杂度：$O(n)$，每个元素最多被左右指针各访问一次。
• 空间复杂度：$O(1)$，仅使用常数个变量。

思考

该解法利用滑动窗口维护当前窗口内 0 和 1 的数量，并在两者都超过 k 时收缩左边界。由于每次收缩后窗口一定满足条件，因此可以放心地累加以当前右端点结尾的所有子串数量。这是一种典型的统计满足条件的子串数量的技巧，比枚举所有子串更高效。代码简洁，逻辑清晰，是本题的标准解法。