Distinct Binary Numbers Inside a String

Hard

You get a string bits of 0 and 1 characters. A binary number can be written out of it by crossing out any characters (possibly none) while keeping the order of the rest, as long as at least one character stays. Such a record is proper if it has no leading zeros: it either starts with 1 or is exactly "0". Return how many different proper records can be obtained this way, modulo 10⁹ + 7.

Example 1

bits='110' → 5

The numbers 1, 0, 11, 10 and 110 can be written out: five distinct ones.

Example 2

bits='0010' → 3

Without leading zeros only 0, 1 and 10 are possible.

Example 3

bits='000' → 1

Constraints

1 ≤ len(bits) ≤ 10⁵
bits consists only of '0' and '1'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

bits='110'

Expected

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