2478. Number of Beautiful Partitions Hard

1/**
2 * [2478] Number of Beautiful Partitions
3 *
4 * You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.
5 * A partition of s is called beautiful if:
6 * 
7 * 	s is partitioned into k non-intersecting substrings.
8 * 	Each substring has a length of at least minLength.
9 * 	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.
10 * 
11 * Return the number of beautiful partitions of s. Since the answer may be very large, return it modulo 10^9 + 7.
12 * A substring is a contiguous sequence of characters within a string.
13 *  
14 * <strong class="example">Example 1:
15 * 
16 * Input: s = "23542185131", k = 3, minLength = 2
17 * Output: 3
18 * Explanation: There exists three ways to create a beautiful partition:
19 * "2354 | 218 | 5131"
20 * "2354 | 21851 | 31"
21 * "2354218 | 51 | 31"
22 * 
23 * <strong class="example">Example 2:
24 * 
25 * Input: s = "23542185131", k = 3, minLength = 3
26 * Output: 1
27 * Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".
28 * 
29 * <strong class="example">Example 3:
30 * 
31 * Input: s = "3312958", k = 3, minLength = 1
32 * Output: 1
33 * Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	1 <= k, minLength <= s.length <= 1000
39 * 	s consists of the digits '1' to '9'.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/number-of-beautiful-partitions/
45// discuss: https://leetcode.com/problems/number-of-beautiful-partitions/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn beautiful_partitions(s: String, k: i32, min_length: i32) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_2478() {
63    }
64}
65