Count the number of substrings of a binary string where one character appears at most times.
Given a binary string and an integer , count how many substrings of satisfy the -constraint.
A substring is valid if at least one of the two characters, '0' or '1', appears at most times inside that substring.
Return the total number of valid substrings.
Input Format
- A binary string
s. - An integer
k.
You may assume both are provided in the standard function-call format used by the platform.
Output Format
- Return a single integer: the number of substrings that satisfy the -constraint.
Constraints
1 <= s.length <= $10^{5}$s[i]is either'0'or'1'0 <= k <= s.length
Example 1
Input
s = "10101", k = 1
Output
10
Explanation
Valid substrings are all substrings except the three length-3 substrings "101", "010", and "101", which contain both characters more than once.
Example 2
Input
s = "111", k = 1
Output
6
Explanation
Every substring is valid because each substring contains zero '0' characters, which is at most 1.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.