Number of Beautiful Partitions — Problem & Solution
Number of Beautiful Partitions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Beautiful Partitions is a hard coding problem on strings, dynamic programming and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of the digits '1' to '9' and two integers k and minLength. A partition of s is beautiful when:
sis split into exactlyknon-overlapping, non-empty substrings that together cover all ofs;- every substring has length at least
minLength; - every substring starts with a prime digit and ends with a non-prime digit. The prime digits are
'2','3','5'and'7'.
Return the number of beautiful partitions of s, modulo 10^9 + 7.
Example 1
Input: s = "29374951", k = 2, minLength = 1
Output: 2
Explanation: `"29" + "374951"` and `"293749" + "51"`. A cut can only go between a non-prime digit and a prime digit.
Example 2
Input: s = "29374951", k = 3, minLength = 2
Output: 1
Explanation: `"29" + "3749" + "51"`.
Example 3
Input: s = "29374951", k = 2, minLength = 3
Output: 0
Explanation: Both two-piece splits leave a piece of length 2.
Constraints
1 <= k, minLength <= s.length <= 1000s consists of the digits '1' to '9'
Hints for Number of Beautiful Partitions
Hint 1
If
sdoes not start with a prime digit or does not end with a non-prime digit, the answer is 0. Otherwise, a cut may go between positionsj - 1andjexactly whens[j-1]is non-prime ands[j]is prime.Hint 2
Let
dp[c][j]be the number of ways to splits[0..j)intocvalid pieces, defined only at legal boundariesj. Thendp[c][j]is the sum ofdp[c-1][p]over legal boundariesp <= j - minLength.Hint 3
That sum is a running prefix sum: as
jgrows, adddp[c-1][j - minLength]to an accumulator. Each layer is O(n), so the whole DP is O(n · k).
How to solve Number of Beautiful Partitions
Every piece starts with a prime and ends with a non-prime, so the boundaries between pieces are forced to be 'non-prime then prime' positions. The problem becomes: choose k - 1 of those legal cut positions so that consecutive boundaries are at least minLength apart — a layered DP whose transition is a prefix sum.
Approach
- Return 0 unless
s[0]is prime ands[n-1]is non-prime. - Mark legal boundaries: 0,
n, and everyjin1..n-1withs[j-1]non-prime ands[j]prime. - Layer 0:
prev[0] = 1. For each of theklayers, sweepjfrom 1 tonwith a running sum: whenj - minLength >= 0, addprev[j - minLength]; ifjis a legal boundary,cur[j] = running. - After
klayers, returnprev[n]modulo 10^9 + 7.
Why it works
A partition into k pieces is a sequence of boundaries 0 = b0 < b1 < … < bk = n. Each piece s[b(i-1)..bi) starts with a prime and ends with a non-prime exactly when every inner boundary is a legal cut (and the two ends of s are right), and has length at least minLength exactly when consecutive boundaries are at least minLength apart. The layered DP counts precisely these sequences, and the running sum adds each earlier boundary once it is far enough behind j.
Complexity
- Time —
O(n · k) - Space —
O(n)
Pitfalls
- Check the first and last digit of
sup front — the boundary rule alone does not cover them. - Only add
prev[p]to the running sum oncep <= j - minLength; adding it earlier allows short pieces. - The naive transition (loop over every earlier boundary) is O(n^2 · k) — too slow for n = 1000.
Reference solution
Python
def beautifulPartitions(s: str, k: int, minLength: int) -> int:
MOD = 10 ** 9 + 7
n = len(s)
primes = set('2357')
if s[0] not in primes or s[-1] in primes:
return 0
legal = [False] * (n + 1)
legal[0] = legal[n] = True
for j in range(1, n):
legal[j] = s[j - 1] not in primes and s[j] in primes
prev = [0] * (n + 1)
prev[0] = 1
for _ in range(k):
cur = [0] * (n + 1)
running = 0
for j in range(1, n + 1):
if j - minLength >= 0:
running = (running + prev[j - minLength]) % MOD
if legal[j]:
cur[j] = running
prev = cur
return prev[n]Java
static boolean isPrimeDigit(char c) {
return c == '2' || c == '3' || c == '5' || c == '7';
}
public static int beautifulPartitions(String s, int k, int minLength) {
final long MOD = 1000000007L;
int n = s.length();
if (!isPrimeDigit(s.charAt(0)) || isPrimeDigit(s.charAt(n - 1))) return 0;
boolean[] legal = new boolean[n + 1];
legal[0] = legal[n] = true;
for (int j = 1; j < n; j++) legal[j] = !isPrimeDigit(s.charAt(j - 1)) && isPrimeDigit(s.charAt(j));
long[] prev = new long[n + 1];
prev[0] = 1;
for (int c = 0; c < k; c++) {
long[] cur = new long[n + 1];
long running = 0;
for (int j = 1; j <= n; j++) {
if (j - minLength >= 0) running = (running + prev[j - minLength]) % MOD;
if (legal[j]) cur[j] = running;
}
prev = cur;
}
return (int) prev[n];
}C++
bool isPrimeDigit(char c) {
return c == '2' || c == '3' || c == '5' || c == '7';
}
int beautifulPartitions(string s, int k, int minLength) {
const long long MOD = 1000000007LL;
int n = s.size();
if (!isPrimeDigit(s[0]) || isPrimeDigit(s[n - 1])) return 0;
vector<bool> legal(n + 1, false);
legal[0] = legal[n] = true;
for (int j = 1; j < n; j++) legal[j] = !isPrimeDigit(s[j - 1]) && isPrimeDigit(s[j]);
vector<long long> prev(n + 1, 0);
prev[0] = 1;
for (int c = 0; c < k; c++) {
vector<long long> cur(n + 1, 0);
long long running = 0;
for (int j = 1; j <= n; j++) {
if (j - minLength >= 0) running = (running + prev[j - minLength]) % MOD;
if (legal[j]) cur[j] = running;
}
prev = cur;
}
return (int)prev[n];
}JavaScript
var beautifulPartitions = function(s, k, minLength) {
var MOD = 1000000007, n = s.length;
var isPrime = function(c) { return c === '2' || c === '3' || c === '5' || c === '7'; };
if (!isPrime(s[0]) || isPrime(s[n - 1])) return 0;
var legal = new Array(n + 1).fill(false);
legal[0] = legal[n] = true;
for (var j = 1; j < n; j++) legal[j] = !isPrime(s[j - 1]) && isPrime(s[j]);
var prev = new Array(n + 1).fill(0);
prev[0] = 1;
for (var c = 0; c < k; c++) {
var cur = new Array(n + 1).fill(0), running = 0;
for (var j = 1; j <= n; j++) {
if (j - minLength >= 0) running = (running + prev[j - minLength]) % MOD;
if (legal[j]) cur[j] = running;
}
prev = cur;
}
return prev[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming