Watch 10 video solutions for Number of Beautiful Partitions, a hard level problem involving String, Dynamic Programming. This walkthrough by NeetCode has 158,858 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.minLength.'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 <= 1000s consists of the digits '1' to '9'.