#2478

Number of Beautiful Partitions

international master · 1905 · lc hard +32 · verified · 32.9% accepted · 371 likes · top 10%

Description

Given a string s of digits '1'–'9' and integers k and minLength, count "beautiful" partitions of s: ways to split it into exactly k non-overlapping substrings each of length ≥ minLength, where each substring begins with a prime digit ('2', '3', '5', or '7') and ends with a non-prime digit. Return the count modulo 10⁹ + 7.

Example 1:

Input: s = "23542185131", k = 3, minLength = 2

Output: 3

Explanation: There exists three ways to create a beautiful partition:

"2354 | 218 | 5131"

"2354 | 21851 | 31"

"2354218 | 51 | 31"

Example 2:

Input: s = "23542185131", k = 3, minLength = 3

Output: 1

Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".

Example 3:

Input: s = "3312958", k = 3, minLength = 1

Output: 1

Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".

Code

1

2

3

class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:

class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int: