FastPrepFastPrep
Problem Brief

Prime String

INTERNOA

Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers. The digits must remain in the order given and the entire string must be used. Each number must be in the range 2 to 106 inclusive, and may not contain leading zeros. Since the answer can be large, return the answer modulo (109 + 7).

Note: The initial string does not contain leading zeros.

Function Description

Complete the function countPrimeStrings in the editor below.

countPrimeStrings has the following parameter(s):

  • string s: a string of digits

Returns

int: the number of ways the string can be split into primes, modulo 1000000007, (109+7)

1Example 1

Input
s = "11375"
Output
3
Explanation

This string can be split into primes 3 different ways: [11, 37, 5], [11, 3, 7, 5], [113, 7, 5].

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ length of s ≤ 105
  • there should be more of them. I will add once find more reliable reference 🐸
public int countPrimeStrings(String s) {
  // write your code here
}
Input

s

"11375"

Output

3

Sign in to submit your solution.