Pieces From Prime to Non-Prime

Hard

You are given a string digits made of the digits 1 through 9, plus numbers pieces and min_len. The digits 2, 3, 5 and 7 are prime; the rest are non-prime. Cut the string into exactly pieces non-empty consecutive pieces so that: - every piece is at least min_len long; - every piece starts with a prime digit and ends with a non-prime one. Count the number of such cuttings. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

digits="2738541", pieces=2, min_len=2 → 1

A new piece can start only at a prime digit preceded by a non-prime one. The only such spot inside the string is before 5 (it follows 8), giving "2738 | 541".

Example 2

digits="21212121", pieces=3, min_len=2 → 3

Cuts are possible before every 2 except the first, at positions 2, 4 and 6. Choosing two of them gives 3 ways, and every piece is at least 2 long.

Example 3

digits="4235", pieces=1, min_len=1 → 0

The string starts with the non-prime 4, so no split works.

Constraints

1 ≤ pieces ≤ len(digits) ≤ 2000
1 ≤ min_len ≤ len(digits)
digits consists of the digits 1 through 9

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="2738541", pieces=2, min_len=2

Expected

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