A Printout With No Spaces

Hard

A program was meant to print a list of integers separated by spaces, but the spaces got lost and all that remains is one string of digits, digits. You know that every number in the list was between 1 and limit inclusive and was written without leading zeros. How many different lists could have produced the string digits? The answer may be large, so return it modulo 10⁹ + 7.

Example 1

digits="2105", limit=30 → 1

A zero can neither be a number on its own nor start one, so it must follow the 1: [2, 10, 5]. That is the only option.

Example 2

digits="1111", limit=11 → 5

The splits are [1, 1, 1, 1], [11, 1, 1], [1, 11, 1], [1, 1, 11] and [11, 11], five in total.

Example 3

digits="700", limit=99 → 0

A zero can neither stand alone nor start a number, and 700 exceeds 99, so there is no valid split.

Constraints

1 ≤ len(digits) ≤ 10⁵
digits contains only digits and does not start with 0
1 ≤ limit ≤ 10⁹

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

digits="2105", limit=30

Expected

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