Skip to main content
Talentd

Number of Beautiful Partitions - Solution & Explanation

HardStringDynamic Programming22 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

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.

Approach 1: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(kn), where n is the length of the string. The space complexity is O(n).

Try this approach in the editor →

Approach 2: Recursive with Memoization

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n^2 * k) with the memoization of overlapping subproblems. The space complexity is O(n*k).

Try this approach in the editor →

Approach 3: Dynamic Programming

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:

  1. The ith character is a non-prime number;
  2. The 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

The time complexity is O(kn), where n is the length of the string. The space complexity is O(n).

Recursive with Memoization

The time complexity is O(n^2 * k) with the memoization of overlapping subproblems. The space complexity is O(n*k).

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(n * k)O(n * k)When first modeling the partition problem recursively or explaining the state transitions during interviews
Dynamic Programming with Prefix OptimizationO(n * k)O(n * k)General case and interview‑ready solution that avoids repeated range scans

Video Solution

2478. Number of Beautiful Partitions | Weekly 320 | LeetCode 2478 • Bro Coders • 1,480 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Number of Beautiful Partitions easy or hard?
Number of Beautiful Partitions is classified as a Hard problem on LeetCode. The difficulty comes from combining string constraints with dynamic programming and optimizing transitions to avoid O(n^2 * k) behavior.
Number of Beautiful Partitions Python/Java solution
Python and Java implementations typically build a DP table with nested loops over partition counts and string indices. A helper function checks whether a digit is prime (2,3,5,7). Prefix sums are used to aggregate previous states quickly, keeping the runtime O(n * k).
How to solve Number of Beautiful Partitions in O(n * k)?
Precompute valid partition boundaries where a non‑prime digit is followed by a prime digit. Build a DP table where dp[i][j] represents ways to create j partitions using the first i characters. Use prefix sums to accumulate transitions efficiently so each partition layer processes the string in linear time.
What is the best approach for Number of Beautiful Partitions?
Dynamic programming with prefix sum optimization is the most efficient approach. It tracks how many ways the first i characters can form j valid partitions while enforcing prime start digits and non‑prime endings. The method runs in O(n * k) time and avoids repeatedly scanning previous split positions.
Is Number of Beautiful Partitions asked at Google/Amazon/Meta?
Problems involving constrained string partitioning and dynamic programming commonly appear in interviews at companies like Google, Amazon, and Meta. This specific problem tests DP state design, boundary validation, and optimization using prefix sums.
What data structure is used in Number of Beautiful Partitions?
The core data structure is a 2D dynamic programming table indexed by string position and partition count. Prefix sum arrays are often added to speed up range transitions between valid partition points.
What is the time complexity of Number of Beautiful Partitions?
The optimal dynamic programming solution runs in O(n * k) time, where n is the length of the string and k is the number of required partitions. Space complexity is also O(n * k) for storing DP states that represent prefix lengths and partition counts.

Ready to solve this problem?

Practice Number of Beautiful Partitions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Ways to Separate Numbers

Next

Restore The Array