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

Правка en2, от alpha_1001, 2021-11-15 04:42:03
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...

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

Feel free to share your approach.

Теги #counting, #dynamic programming, #faang, #online assessment

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский alpha_1001 2021-11-16 04:35:23 437
en3 Английский alpha_1001 2021-11-15 06:28:40 225
en2 Английский alpha_1001 2021-11-15 04:42:03 0 (published)
en1 Английский alpha_1001 2021-11-15 04:40:19 669 This was asked in one of FAANG company. (saved to drafts)