3258. Count Substrings That Satisfy K-Constraint I

Posted on Edited on In

3258. Count Substrings That Satisfy K-Constraint I

Description

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:

1
2
3
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:

1
2
3
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:

1
2
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'.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int res = 0, left = 0;
        vector<int> count(2, 0);
        // the meaning of sliding window: all the valid substring ending with s[right]
        for (int right = 0; right < s.size(); right++) {
            int val = s[right] - '0';
            count[val % 2]++;
            while (count[0] > k && count[1] > k) {
                val = s[left] - '0';
                count[val % 2]--;
                left++;
            }
            res += right + 1 - left;
        }
        return res;
    }
};