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

为保证权益，题目请参考 3258. 统计满足 K 约束的子字符串数量 I(From LeetCode).

解决方案1

说明

在该问题中，考虑到1 <= s.length <= 50，因此即使遍历所以的子串也只有$2500$数量级，大概率可以直接遍历。而且，可以通过数据预处理或者滑动窗口的方式进行优化子串的计算方式。

Python

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:

        zero_accu = [0] * len(s)
        zero_accu[0] = 1 if s[0] == "0" else 0
        for i in range(1, len(s)):
            zero_accu[i] = zero_accu[i - 1] + (1 if s[i] == "0" else 0)

        one_accu = [0] * len(s)
        one_accu[0] = 1 if s[0] == "1" else 0
        for i in range(1, len(s)):
            one_accu[i] = one_accu[i - 1] + (1 if s[i] == "1" else 0)

        ans = 0
        for i in range(len(s)):
            for j in range(i, len(s)):
                if i == 0:
                    a = zero_accu[j]
                    b = one_accu[j]
                else:
                    a = zero_accu[j] - zero_accu[i - 1]
                    b = one_accu[j] - one_accu[i - 1]

                if a <= k or b <= k:
                    ans += 1

        return ans