Count the Ways to Split a Digit String into Primes
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
You are given a string `s` consisting of decimal digits (`'0'`–`'9'`) that represents a positive integer. Count the number of ways to split `s` into a sequence of contiguous, non-empty segments such that **every segment, read as a decimal integer, is a prime number**.
A valid split must satisfy all of the following:
1. **Order is preserved.** Segments are read left to right; you may not reorder digits.
2. **Every character is used exactly once.** The concatenation of the segments, in order, must equal `s` — no characters are skipped or repeated.
3. **Each segment is prime.** Reading a segment as a base-10 integer must yield a prime number (`2, 3, 5, 7, 11, 13, ...`).
4. **No leading zeros.** A segment of length greater than 1 may not start with `'0'` (e.g., `"03"` is not a valid segment). Note that `"0"` and `"1"` are not prime anyway.
Two splits are considered different if the set of cut positions differs.
Because the count can be very large, return it **modulo `1_000_000_007`**.
### Input
- `s`: a non-empty string of decimal digits.
### Output
- An integer: the number of valid prime splits of `s`, taken modulo `1_000_000_007`.
### Examples
**Example 1**
```
Input: s = "11375"
Output: 3
Explanation: The valid splits are:
[11, 37, 5]
[11, 3, 7, 5]
[113, 7, 5]
```
**Example 2**
```
Input: s = "2"
Output: 1
Explanation: "2" is itself prime, giving the single split [2].
```
**Example 3**
```
Input: s = "4"
Output: 0
Explanation: "4" is not prime, and there is no other way to split a single
character, so there are 0 valid splits.
```
**Example 4**
```
Input: s = "13"
Output: 1
Explanation: [13] is valid because 13 is prime. The split [1, 3] is invalid
because 1 is not prime, so there is exactly one valid split.
```
### Constraints
- `1 <= len(s) <= 1000`
- `s` contains only the characters `'0'`–`'9'`.
- A single segment may be long, so its integer value can exceed 64-bit range; an
efficient primality test (for example, a deterministic Miller–Rabin) is expected
rather than naive trial division on the full value.
Quick Answer: This question evaluates dynamic programming combined with number theory, specifically counting valid partitions of a digit string under a primality constraint. It tests designing a state-transition recurrence paired with an efficient primality check for large values, a combination commonly used to assess practical algorithmic reasoning in coding interviews.
You are given a string `s` consisting of decimal digits (`'0'`-`'9'`) that represents a positive integer. Count the number of ways to split `s` into a sequence of contiguous, non-empty segments such that **every segment, read as a decimal integer, is a prime number**.
A valid split must satisfy all of the following:
1. **Order is preserved.** Segments are read left to right; you may not reorder digits.
2. **Every character is used exactly once.** The concatenation of the segments, in order, must equal `s` - no characters are skipped or repeated.
3. **Each segment is prime.** Reading a segment as a base-10 integer must yield a prime number (`2, 3, 5, 7, 11, 13, ...`).
4. **No leading zeros.** A segment of length greater than 1 may not start with `'0'` (e.g., `"03"` is not a valid segment). Note that `"0"` and `"1"` are not prime anyway.
Two splits are considered different if the set of cut positions differs. Because the count can be very large, return it **modulo `1_000_000_007`**.
**Approach:** Let `dp[i]` be the number of valid prime splits of the suffix `s[i:]`. Then `dp[n] = 1` (empty suffix), and for each `i`, `dp[i] = sum(dp[j+1])` over every `j >= i` such that `s[i..j]` is a prime with no leading zero. Answer is `dp[0]`. A segment can be very long, so use an efficient primality test (deterministic Miller-Rabin) rather than trial division on the full value.
**Examples:**
- `s = "11375"` -> `3` (splits `[11,37,5]`, `[11,3,7,5]`, `[113,7,5]`)
- `s = "2"` -> `1`
- `s = "4"` -> `0`
- `s = "13"` -> `1` (only `[13]`; `[1,3]` is invalid since 1 is not prime)
Constraints
- 1 <= len(s) <= 1000
- s contains only the characters '0'-'9'
- A single segment may be long, so its integer value can exceed 64-bit range; use an efficient primality test (e.g. deterministic Miller-Rabin) rather than naive trial division on the full value
- Return the count modulo 1_000_000_007
Examples
Input: ('11375',)
Expected Output: 3
Explanation: Valid splits: [11,37,5], [11,3,7,5], [113,7,5].
Input: ('2',)
Expected Output: 1
Explanation: "2" is itself prime, the single split [2].
Input: ('4',)
Expected Output: 0
Explanation: 4 is not prime and a single character cannot be split further.
Input: ('13',)
Expected Output: 1
Explanation: [13] is valid; [1,3] is invalid because 1 is not prime.
Input: ('23',)
Expected Output: 2
Explanation: [23] (23 is prime) and [2,3] (both prime) are both valid.
Input: ('0',)
Expected Output: 0
Explanation: Edge case: '0' is not prime and cannot start a valid segment, so there are 0 splits.
Input: ('37',)
Expected Output: 2
Explanation: [37] and [3,7] are both valid.
Input: ('22',)
Expected Output: 1
Explanation: 22 = 2*11 is not prime, so only the single-digit split [2,2] works.
Input: ('3737',)
Expected Output: 6
Explanation: Larger case combining many prime substrings such as 37, 3, 7, 373, 73.
Input: ('113137',)
Expected Output: 8
Explanation: Larger case exercising multi-digit primes like 113, 131, 13, 31, 137.
Hints
- Define dp[i] = number of valid prime splits of the suffix s[i:]. The answer is dp[0], with the base case dp[n] = 1 for the empty suffix.
- For each start index i, extend the segment one digit at a time to build its integer value incrementally; add dp[j+1] whenever s[i..j] is prime. If s[i] == '0', no segment can start there (single '0' isn't prime, longer segments have a leading zero), so dp[i] = 0.
- Segments can be hundreds of digits long, so ordinary trial division is too slow. Use deterministic Miller-Rabin (Python's pow(a, d, num) handles big integers) and remember to take the count modulo 1_000_000_007.