3258. Count Substrings That Satisfy K-Constraint I
Easy78.8% acceptance56,431 / 71,568 submissions
Asked by 1 company
Topics
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 mostk. - The number of
1's in the string is at mostk.
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 <= 501 <= k <= s.lengths[i]is either'0'or'1'.
Hints
Hint 1
Using a brute force approach, check each index until a substring satisfying the k-constraint is found, then increment.