当前位置：首页 > article >正文

LeetCode每日一题3258---统计满足 K 约束的子字符串数量 I

article 2024/11/13 13:09:30

一、题目描述

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

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

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

示例 1：
输入：s = “10101”, k = 1

输出：12

解释：
s 的所有子字符串中，除了 “1010”、“10101” 和 “0101” 外，其余子字符串都满足 k 约束。

示例 2：
输入：s = “1010101”, k = 2

输出：25

解释：
s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：
输入：s = “11111”, k = 1

输出：15

解释：
s 的所有子字符串都满足 k 约束。

提示：
1 <= s.length <= 50
1 <= k <= s.length
s[i] 是 ‘0’ 或 ‘1’。

二、解题思路

这道题目可以利用了滑动窗口的技巧来维护一个动态的子串区间 [l, i]，并确保窗口内的 ‘1’ 和 ‘0’ 的数量都不超过 k。滑动窗口可以高效地解决这种类型的子串计数问题。

当窗口内的 ‘1’ 或 ‘0’ 的数量超过 k 时，窗口左边（l）会被向右移动，直到窗口变得有效。
每当窗口有效时，表示从 l 到 i 的子串都符合条件，因此将它们的数量（即 i - l + 1）加到结果中。

三、代码

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int l = 0;
        int count = 0;
        int one = 0;
        int zero = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') one++;
            else zero++;
            while (one > k && zero > k) {
                if (s[l++] == '1') one--;
                else zero--;
            }
            count += i - l + 1;
        }
        return count;
    }
};