[LeetCode] 3258. Count Substrings That Satisfy K-Constraint I

You are given a binary string s and an integer k.

A binary string satisfies the k-constraint if either of the following conditions holds:
The number of 0’s in the string is at most k.
The number of 1’s in the string is at most k.

Return an integer denoting the number of substrings of s that satisfy the k-constraint.

Example 1:
Input: s = “10101”, k = 1
Output: 12

Explanation:
Every substring of s except the substrings “1010”, “10101”, and “0101” satisfies the k-constraint.

Example 2:
Input: s = “1010101”, k = 2
Output: 25

Explanation:
Every substring of s except the substrings with a length greater than 5 satisfies the k-constraint.

Example 3:
Input: s = “11111”, k = 1
Output: 15

Explanation:
All substrings of s satisfy the k-constraint.

Constraints:
1 <= s.length <= 50
1 <= k <= s.length
s[i] is either ‘0’ or ‘1’.

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

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

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

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

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

思路

思路是滑动窗口。注意这道题要我们找的是满足如下这两个条件之一就行的子串。所以代码中只要跳出 while 循环，就可以累加结果。

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

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        int zero = 0;
        int one = 0;
        int start = 0;
        int end = 0;
        int res = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (c1 == '1') {
                one++;
            } else {
                zero++;
            }
            end++;
            while (zero > k && one > k) {
                char c2 = s.charAt(start);
                if (c2 == '1') {
                    one--;
                } else {
                    zero--;
                }
                start++;
            }
            res += end - start;
        }
        return res;
    }
}