Help in this Counting Problem. Was asked in one of the FAANG OA.
Difference between en2 and en3, changed 225 character(s)
~~~~~↵
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.`↵

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)