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'.Problem Overview: You are given a numeric string s. Split it into exactly k substrings where each substring has length ≥ minLength, starts with a prime digit (2,3,5,7), and ends with a non‑prime digit. The goal is to count how many such valid partitionings exist.
Approach 1: Recursive with Memoization (Top‑Down DP) (Time: O(n * k), Space: O(n * k))
This approach models the problem as a decision process over partition boundaries. Starting from index i, you attempt to create the next partition if the character is a valid prime start. For each possible endpoint satisfying minLength and the non‑prime ending rule, recursively compute the number of ways to form the remaining k-1 partitions. Memoization caches results for states defined by (index, remainingPartitions) to avoid recomputing overlapping subproblems. The recursion naturally fits the structure of the problem but still relies on pruning invalid starts and respecting minimum length constraints. This pattern is common in dynamic programming problems over string partitioning.
Approach 2: Dynamic Programming with Prefix Optimization (Time: O(n * k), Space: O(n * k))
The optimized solution converts the recursion into a bottom‑up DP table. Let dp[i][j] represent the number of ways to form j valid partitions using the first i characters. A partition boundary is only valid if the previous character is non‑prime and the next character is prime. Precompute all valid split positions, then iterate over partition counts while maintaining prefix sums to quickly accumulate transitions. This avoids scanning all previous indices for every state. The algorithm processes the string once per partition count, which keeps the complexity at O(n * k). This technique frequently appears in advanced DP problems where transitions depend on ranges rather than single states.
Recommended for interviews: The bottom‑up dynamic programming approach is the expected solution. It demonstrates that you can translate recursive partition logic into an efficient iterative DP and optimize transitions with prefix sums. The memoized recursion is still valuable because it shows how to reason about the state definition and constraints before optimizing.
This approach makes use of dynamic programming to calculate the number of beautiful partitions. We will create a DP array where DP[i] represents the number of ways to partition the substring up to index i. We iterate over possible partition start points and check if each substring meets the beautiful partition criteria, updating our DP table accordingly.
This code first checks if it is even possible to partition the string into k parts given the minimum length constraint. It then iterates over possible partitions using a dynamic programming array to store the number of partitions ending at each index.
The time complexity is O(kn), where n is the length of the string. The space complexity is O(n).
This solution leverages a recursive approach combined with memoization. The function repeatedly partitions the string by recursively trying each valid partition endpoint and memorizes already computed results to avoid redundant calculations.
This code implements recursive partitioning using memoization. For each recursive call, it checks the number of partitions remaining and aligns the further partitions recursively while saving computed states in a memo array to optimize and reduce redundancy.
The time complexity is O(n^2 * k) with the memoization of overlapping subproblems. The space complexity is O(n*k).
We define f[i][j] as the number of schemes for dividing the first i characters into j sections. Initialize f[0][0] = 1, and the rest f[i][j] = 0.
First, we need to determine whether the ith character can be the last character of the jth section, it needs to meet the following conditions simultaneously:
ith character is a non-prime number;i+1th character is a prime number, or the ith character is the last character of the entire string.If the ith character cannot be the last character of the jth section, then f[i][j]=0. Otherwise, we have:
$
f[i][j]=sum_{t=0}^{i-minLength}f[t][j-1]
That is to say, we need to enumerate which character is the end of the previous section. Here we use the prefix sum array g[i][j] = sum_{t=0}^{i}f[t][j] to optimize the time complexity of enumeration.
Then we have:
f[i][j]=g[i-minLength][j-1]
The time complexity is O(n times k), and the space complexity is O(n times k). Where n and k are the length of the string s$ and the number of sections to be divided, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | The time complexity is |
| Recursive with Memoization | The time complexity is |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * k) | O(n * k) | When first modeling the partition problem recursively or explaining the state transitions during interviews |
| Dynamic Programming with Prefix Optimization | O(n * k) | O(n * k) | General case and interview‑ready solution that avoids repeated range scans |
2478. Number of Beautiful Partitions | Weekly 320 | LeetCode 2478 • Bro Coders • 1,455 views views
Watch 8 more video solutions →Practice Number of Beautiful Partitions with our built-in code editor and test cases.
Practice on FleetCode