Few Zeros or Few Ones: Range Queries

Hard

You are given a string bits made of 0 and 1 characters and an integer cap. Call a string lopsided if it has at most cap zeros **or** at most cap ones (either condition is enough). You also get a list of queries ranges, each a pair [l, r]. For a query, take the piece bits[l..r] (both ends included) and count how many of its substrings are lopsided. Substrings at different positions count separately. Return the answers in the same order as the queries.

Example 1

bits="00110", cap=1, ranges=[[0, 4], [1, 3]] → [12, 6]

The whole string has 15 substrings; "0011", "00110" and "0110" fail since each has at least two zeros and two ones, leaving 12. In the piece "011" all 6 substrings are lopsided.

Example 2

bits="1", cap=1, ranges=[[0, 0]] → [1]

The only substring, "1", contains no zeros.

Constraints

1 ≤ len(bits) ≤ 10⁵
Every character of bits is 0 or 1
1 ≤ cap ≤ len(bits)
1 ≤ len(ranges) ≤ 10⁵
0 ≤ l ≤ r < len(bits)
All queries are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array String Binary Search Prefix Sum Sliding Window

Similar problems

Shortest Stretch Reaching a Total Hard Berry Walk Along a Path Hard Sum Times Length Under a Limit Hard Longest Affordable Run of Machines Hard Signal in the Remotest Village Hard

Input

bits="00110", cap=1, ranges=[[0, 4], [1, 3]]

Expected

[12, 6]

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.