g2401_2500.s2478_number_of_beautiful_partitions

Class Solution

java.lang.Object

g2401_2500.s2478_number_of_beautiful_partitions.Solution

public class Solution
extends Object

2478 - Number of Beautiful Partitions.

Hard

You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.

A partition of s is called beautiful if:

• s is partitioned into k non-intersecting substrings.
• Each substring has a length of at least minLength.
• Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are '2', '3', '5', and '7', and the rest of the digits are non-prime.

Return the number of beautiful partitions of s. Since the answer may be very large, return it modulo 109 + 7.

A substring is a contiguous sequence of characters within a string.

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”.

Constraints:

• 1 <= k, minLength <= s.length <= 1000
• s consists of the digits '1' to '9'.

Constructor Summary

Constructors

Constructor and Description
Solution()

Method Summary

Modifier and Type	Method and Description
int	beautifulPartitions(String s, int k, int l)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Solution

public Solution()

Method Detail

beautifulPartitions

public int beautifulPartitions(String s,
                               int k,
                               int l)