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

#python #leetcode #sliding-window

题目描述¶

关联：https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-i/description/

题目描述

给你一个二进制字符串 s 和一个整数 k。

如果一个二进制字符串满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。

返回一个整数，表示 s 的所有满足 k 约束的子字符串的数量。

注意，这道题对应的第二题不仅仅是增大了范围，而是改了题目，

见 3261. 统计满足 K 约束的子字符串数量 II

解题思路¶

暴力解法¶

直接暴力：

from operator import getitem
from itertools import starmap, combinations, repeat

def subslices(seq):
    """Return all contiguous non-empty subslices of a sequence."""
    # subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D
    return map(
        getitem,
        repeat(seq),
        starmap(slice, combinations(range(len(seq) + 1), 2))
    )

def count_substrings(s: str, k: int) -> int:    
    return sum(
        True
        for substr in subslices(s)
        if substr.count('0') <= k or substr.count('1') <= k
    )

慢是慢了点，但是他好看啊（

滑动窗口¶

可以使用滑动窗口算法来统计满足 k 约束的子字符串数量。具体步骤如下：

初始化变量 result 用于存储满足条件的子字符串数量，left 用于滑动窗口的左边界，count_0 和 count_1 分别用于统计窗口内 0 和 1 的数量。
遍历字符串 s，使用 right 作为滑动窗口的右边界。
对于每个字符 char，根据其值更新对应的计数。
如果窗口内 0 和 1 的数量都大于 k，则需要缩小窗口，即左边界右移，并同时更新计数。
计算以 right 为右边界的所有满足条件的子字符串数量，并累加到 result 中。

完整题解¶

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        result = 0
        left = 0
        count_0, count_1 = 0, 0

        for right, char in enumerate(s):

            if char == '0':
                count_0 += 1
            else:
                count_1 += 1

            while count_0 > k and count_1 > k:
                if s[left] == '0':
                    count_0 -= 1
                else:
                    count_1 -= 1
                left += 1

            # 以 right 为右边界返回子字符串的个数
            result += (right - left + 1)

        return result

复杂度分析¶

时间复杂度：\(O(n)\)，其中 \(n\) 是字符串 s 的长度。
空间复杂度：\(O(1)\)。