FastPrep
Problem · Dynamic Programming

Prime String

Learn this problem
● MediumSnowflake logoSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

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

countPrimeStrings(s: String) → int

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)

Examples

Example 1

s = "11375"return = 3

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

Constraints

  • 1 ≤ length of s ≤ 105
  • there should be more of them. I will add once find more reliable reference 🐸

More Snowflake problems

drafts saved locally
public int countPrimeStrings(String s) {
  // write your code here
}
s"11375"
expected3
checking account