Pieces With a Fixed Zero-to-One Ratio

Medium

You are given a binary string bits and two positive integers zeros_part and ones_part. A non-empty contiguous piece of the string fits if its count of zeros and its count of ones are in the proportion zeros_part : ones_part, that is, zeros · ones_part == ones · zeros_part. For instance, with the ratio 2 : 3 both "00111" and "0110011110" fit, while "11100" does not. Count the fitting pieces. Pieces with the same content at different positions are counted separately.

Example 1

bits='1001', zeros_part=1, ones_part=1 → 3

Zeros and ones are equal in "10" (start), "01" (end) and the whole "1001": 3 in total.

Example 2

bits='0010', zeros_part=2, ones_part=1 → 2

Two zeros per one: "001" and "010".

Example 3

bits='111', zeros_part=1, ones_part=3 → 0

There are no zeros, yet the ratio needs at least one: the answer is 0.

Constraints

1 ≤ len(bits) ≤ 10⁵
bits contains only 0 and 1
1 ≤ zeros_part, ones_part ≤ len(bits)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Math String Prefix Sum

Similar problems

Pieces With Matching Ends Medium Even Vowel and Consonant Pieces Medium Balanced Stretches of a String Hard Number in Roman Numerals Medium Fraction as a Decimal Medium

Input

bits='1001', zeros_part=1, ones_part=1

Expected

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