Count Substrings That Satisfy K-Constraint I
EasyStringSliding Window
Solution
export function countKConstraintSubstrings(s: string, k: number): number {
let answer = 0;
let [one, zero] = [0, 0];
let left = 0;
for (let right = 0; right < s.length; right++) {
if (s[right] === '0') {
zero += 1;
} else {
one += 1;
}
while (k < zero && k < one) {
if (s[left] === '0') {
zero -= 1;
} else {
one -= 1;
}
left += 1;
}
answer += right - left + 1;
}
return answer;
}
Complexity
- Time:
O(N)
- Space:
O(1)