Number of Beautiful Partitions

Hard
1522.

Number of Beautiful Partitions

Number of Beautiful Partitions is a hard coding problem on strings, dynamic programming and prefix sum, asked in Amazon and Google interviews.

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:

  • s is split into exactly k non-overlapping, non-empty substrings that together cover all of s;
  • 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 <= 1000
  • s consists of the digits '1' to '9'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @param {number} minLength
 * @return {number}
 */
var beautifulPartitions = function(s, k, minLength) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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:

  • s is split into exactly k non-overlapping, non-empty substrings that together cover all of s;
  • 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 <= 1000
  • s consists of the digits '1' to '9'

Hints for Number of Beautiful Partitions

  1. Hint 1

    If s does 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 positions j - 1 and j exactly when s[j-1] is non-prime and s[j] is prime.

  2. Hint 2

    Let dp[c][j] be the number of ways to split s[0..j) into c valid pieces, defined only at legal boundaries j. Then dp[c][j] is the sum of dp[c-1][p] over legal boundaries p <= j - minLength.

  3. Hint 3

    That sum is a running prefix sum: as j grows, add dp[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

  1. Return 0 unless s[0] is prime and s[n-1] is non-prime.
  2. Mark legal boundaries: 0, n, and every j in 1..n-1 with s[j-1] non-prime and s[j] prime.
  3. Layer 0: prev[0] = 1. For each of the k layers, sweep j from 1 to n with a running sum: when j - minLength >= 0, add prev[j - minLength]; if j is a legal boundary, cur[j] = running.
  4. After k layers, return prev[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 s up front — the boundary rule alone does not cover them.
  • Only add prev[p] to the running sum once p <= 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