Help in this Counting Problem. Was asked in one of the FAANG OA.

Revision en3, by alpha_1001, 2021-11-15 06:28:40
Given a string **S** consisting of digits [0-9], count the number of ways this string can be split into continuous substrings such that each substring is a prime number. Each digit must be in one substring and the entire string must be used.

**Constraints**
1 <= | S | <= 1e5

**Example**
_input_
11373
_output_
6
_Explanation_
[11, 3, 7, 3], [11, 3, 73], [11, 37, 3], [113, 7, 3], [113, 73], [11, 373].


Can anyone help me out?
Thanks in advance.
Happy Coding...

#### UPD:
**Note:**
The input string does not contain leading zeros.
Each number split of the given number must be in the range `2 to 1e6` inclusive.
Since the answer can be large, return the answer modulo `1e9+7`.
 

P.S.: This is my first blog, so correct me if I'm wrong anywhere.

Feel free to share your approach.

Tags #counting, #dynamic programming, #faang, #online assessment

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English alpha_1001 2021-11-16 04:35:23 437
en3 English alpha_1001 2021-11-15 06:28:40 225
en2 English alpha_1001 2021-11-15 04:42:03 0 (published)
en1 English alpha_1001 2021-11-15 04:40:19 669 This was asked in one of FAANG company. (saved to drafts)