#3261

Count Substrings That Satisfy K-Constraint II

hard · 23.4% accepted · 140 likes · top 3%

array · string · binary search · sliding window · prefix sum

⊣ practice⊣ open on leetcode ↗

Description

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

You are also given a 2D integer array queries, where queries[i] = [li, ri].

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 array answer, where answer[i] is the number of substrings of s[li..ri] that satisfy the k-constraint.

Solution