2478. Number of Beautiful Partitions Solution

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 10⁹ + 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.

Python

def is_prime(c):
    return c in {'2', '3', '5', '7'}

def beautiful_partitions(s, k, min_length):
    MOD = 1000000007
    n = len(s)
    if n < k * min_length:
        return 0

    dp = [0] * (n + 1)
    dp[0] = 1

    for _ in range(k):
        new_dp = [0] * (n + 1)
        for i in range(n + 1):
            new_dp[i] = dp[i]
            if i >= min_length and is_prime(s[i - min_length]) and not is_prime(s[i - 1]):
                new_dp[i] = (new_dp[i] + dp[i - min_length]) % MOD
        dp = new_dp

    return dp[n]

print(beautiful_partitions('23542185131', 3, 2))

Java

import java.util.*;

public class Main {
    static final int MOD = 1000000007;

    public static boolean isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    public static int beautifulPartitions(String s, int k, int minLength) {
        int n = s.length();
        if (n < k * minLength) return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int partition = 1; partition <= k; partition++) {
            int[] newDP = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                newDP[i] = dp[i];
                if (i >= minLength && isPrime(s.charAt(i - minLength)) && !isPrime(s.charAt(i - 1))) {
                    newDP[i] = (newDP[i] + dp[i - minLength]) % MOD;
                }
            }
            dp = newDP;
        }

        return dp[n];
    }

    public static void main(String[] args) {
        String s = "23542185131";
        int k = 3, minLength = 2;
        System.out.println(beautifulPartitions(s, k, minLength));
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

bool isPrime(char c) {
    return c == '2' || c == '3' || c == '5' || c == '7';
}

int beautifulPartitions(string s, int k, int minLength) {
    int n = s.length();
    if (n < k * minLength) return 0;

    vector<int> dp(n + 1, 0);  
    dp[0] = 1;

    for (int partition = 1; partition <= k; ++partition) {
        vector<int> newDP(n + 1, 0);
        for (int i = 0; i <= n; ++i) {
            newDP[i] = dp[i];
            if (i >= minLength && isPrime(s[i - minLength]) && !isPrime(s[i - 1])) {
                newDP[i] = (newDP[i] + dp[i - minLength]) % MOD;
            }
        }
        swap(dp, newDP);
    }

    return dp[n];
}

int main() {
    string s = "23542185131";
    int k = 3, minLength = 2;
    cout << beautifulPartitions(s, k, minLength) << endl;
    return 0;
}

JavaScript

function isPrime(c) {
    return ['2', '3', '5', '7'].includes(c);
}

function beautifulPartitions(s, k, minLength) {
    const MOD = 1000000007;
    const n = s.length;
    if (n < k * minLength) return 0;

    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (let partition = 1; partition <= k; partition++) {
        let newDp = new Array(n + 1).fill(0);
        for (let i = 0; i <= n; i++) {
            newDp[i] = dp[i];
            if (i >= minLength && isPrime(s[i - minLength]) && !isPrime(s[i - 1])) {
                newDp[i] = (newDp[i] + dp[i - minLength]) % MOD;
            }
        }
        dp = newDp;
    }

    return dp[n];
}

console.log(beautifulPartitions("23542185131", 3, 2));

#include <stdio.h>
#include <stdbool.h>
#define MOD 1000000007

bool isPrimeDigit(char c) {
  return c == '2' || c == '3' || c == '5' || c == '7';
}

int beautifulPartitions(char* s, int k, int minLength) {
  int n = strlen(s);
  if (n < k * minLength) return 0;

  int dp[n + 1];
  memset(dp, 0, sizeof(dp));
  dp[0] = 1; // Base case

  for (int partition = 1; partition <= k; partition++) {
    int newDP[n + 1];
    memset(newDP, 0, sizeof(newDP));

    for (int i = 0; i <= n; i++) {
      newDP[i] = dp[i];
      if (i >= minLength && isPrimeDigit(s[i - minLength]) && !isPrimeDigit(s[i - 1])) {
        newDP[i] = (newDP[i] + dp[i - minLength]) % MOD;
      }
    }
    memcpy(dp, newDP, sizeof(newDP));
  }
  return dp[n];
}

int main() {
  char s[] = "23542185131";
  int k = 3, minLength = 2;
  printf("%d\n", beautifulPartitions(s, k, minLength));
  return 0;
}

using System;

public class Program {
    const int MOD = 1000000007;

    public static bool IsPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }
    
    public static int BeautifulPartitions(string s, int k, int minLength) {
        int n = s.Length;
        if (n < k * minLength) return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int partition = 1; partition <= k; partition++) {
            int[] newDP = new int[n + 1];
            for (int i = 0; i <= n; i++){
                newDP[i] = dp[i];
                if (i >= minLength && IsPrime(s[i - minLength]) && !IsPrime(s[i - 1])) {
                    newDP[i] = (newDP[i] + dp[i - minLength]) % MOD;
                }
            }
            dp = newDP;
        }

        return dp[n];
    }

    public static void Main() {
        string s = "23542185131";
        int k = 3, minLength = 2;
        Console.WriteLine(BeautifulPartitions(s, k, minLength));
    }
}

This Python solution adopts the dynamic programming approach, emphasizing state transition and update logic to calculate valid partitions count, making extensive use of Python's list operations for efficient index-based management.

Complexity

The time complexity is O(kn) and space complexity is O(n), relying on dynamic programming methodologies and array storage.

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.

Python

def is_prime(c):
    return c in {'2', '3', '5', '7'}

def dfs(s, left_index, k, min_length, memo):
    if k == 1:
        return int(len(s) - left_index >= min_length and is_prime(s[left_index]) and not is_prime(s[-1]))

    if memo[left_index][k] != -1:
        return memo[left_index][k]

    ways = 0
    for i in range(left_index + min_length, len(s)):
        if is_prime(s[left_index]) and not is_prime(s[i - 1]):
            ways = (ways + dfs(s, i, k - 1, min_length, memo)) % (10**9 + 7)

    memo[left_index][k] = ways
    return ways


def beautiful_partitions(s, k, min_length):
    memo = [[-1] * (k + 1) for _ in range(len(s))]
    return dfs(s, 0, k, min_length, memo)

print(beautiful_partitions("23542185131", 3, 2))

Java

import java.util.*;

public class Main {
    static final int MOD = 1000000007;

    static boolean isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    public static int dfs(String s, int leftIndex, int k, int minLength, int[][] memo) {
        int n = s.length();
        if (k == 1) {
            return (n - leftIndex >= minLength && isPrime(s.charAt(leftIndex)) && !isPrime(s.charAt(n - 1))) ? 1 : 0;
        }

        if (memo[leftIndex][k] != -1) return memo[leftIndex][k];

        int result = 0;
        for (int i = leftIndex + minLength; i < n; ++i) {
            if (isPrime(s.charAt(leftIndex)) && !isPrime(s.charAt(i - 1))) {
                result = (result + dfs(s, i, k - 1, minLength, memo)) % MOD;
            }
        }
        memo[leftIndex][k] = result;
        return result;
    }

    public static int beautifulPartitions(String s, int k, int minLength) {
        int[][] memo = new int[s.length()][k + 1];
        for(int[] arr : memo) Arrays.fill(arr, -1);
        return dfs(s, 0, k, minLength, memo);
    }

    public static void main(String[] args) {
        String s = "23542185131";
        int k = 3, minLength = 2;
        System.out.println(beautifulPartitions(s, k, minLength));
    }
}

C++

#include <iostream>
#include <vector>
#include <cstring>

#define MOD 1000000007

using namespace std;

bool isPrimeDigit(char c) {
    return c == '2' || c == '3' || c == '5' || c == '7';
}

int dfs(string &s, int leftIndex, int k, int minLength, vector<vector<int>>& memo) {
    int n = s.size();
    if (k == 1) {
        return (n - leftIndex >= minLength && isPrimeDigit(s[leftIndex]) && !isPrimeDigit(s[n - 1])) ? 1 : 0;
    }

    if (memo[leftIndex][k] != -1) return memo[leftIndex][k];

    int result = 0;
    for (int i = leftIndex + minLength; i < n; ++i) {
        if (isPrimeDigit(s[leftIndex]) && !isPrimeDigit(s[i - 1])) {
            result = (result + dfs(s, i, k - 1, minLength, memo)) % MOD;
        }
    }
    memo[leftIndex][k] = result;
    return result;
}

int beautifulPartitions(string s, int k, int minLength) {
    vector<vector<int>> memo(s.size(), vector<int>(k + 1, -1));
    return dfs(s, 0, k, minLength, memo);
}

int main() {
    string s = "23542185131";
    int k = 3, minLength = 2;
    cout << beautifulPartitions(s, k, minLength) << endl;
    return 0;
}

JavaScript

function isPrime(c) {
    return ['2', '3', '5', '7'].includes(c);
}

function dfs(s, leftIndex, k, minLength, memo) {
    const n = s.length;
    if (k === 1) {
        return (n - leftIndex >= minLength && isPrime(s[leftIndex]) && !isPrime(s[n - 1])) ? 1 : 0;
    }

    if (memo[leftIndex][k] !== -1) return memo[leftIndex][k];

    let result = 0;
    for (let i = leftIndex + minLength; i < n; i++) {
        if (isPrime(s[leftIndex]) && !isPrime(s[i - 1])) {
            result = (result + dfs(s, i, k - 1, minLength, memo)) % (10**9 + 7);
        }
    }
    memo[leftIndex][k] = result;
    return result;
}

function beautifulPartitions(s, k, minLength) {
    const memo = Array.from(Array(s.length), () => Array(k + 1).fill(-1));
    return dfs(s, 0, k, minLength, memo);
}

console.log(beautifulPartitions("23542185131", 3, 2));

#include <stdio.h>
#include <string.h>
#define MOD 1000000007

bool isPrimeDigit(char c) {
    return c == '2' || c == '3' || c == '5' || c == '7';
}

int dfs(char* s, int leftIndex, int k, int minLength, int memo[][1001]) {
    int n = strlen(s);
    if (k == 1) {
        return n - leftIndex >= minLength && isPrimeDigit(s[leftIndex]) && !isPrimeDigit(s[n - 1]);
    }

    if (memo[leftIndex][k] != -1) {
        return memo[leftIndex][k];
    }

    int result = 0;
    for (int i = leftIndex + minLength; i < n; ++i) {
        if (isPrimeDigit(s[leftIndex]) && !isPrimeDigit(s[i - 1])) {
            result = (result + dfs(s, i, k - 1, minLength, memo)) % MOD;
        }
    }
    memo[leftIndex][k] = result;
    return result;
}

int beautifulPartitions(char* s, int k, int minLength) {
    int memo[1001][1001];
    memset(memo, -1, sizeof(memo));
    return dfs(s, 0, k, minLength, memo);
}

int main() {
    char s[] = "23542185131";
    int k = 3, minLength = 2;
    printf("%d\n", beautifulPartitions(s, k, minLength));
    return 0;
}

using System;
using System.Collections.Generic;

public class Program {
    const int MOD = 1000000007;

    public static bool IsPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    public static int Dfs(string s, int leftIndex, int k, int minLength, int[,] memo) {
        int n = s.Length;
        if (k == 1) {
            return n - leftIndex >= minLength && IsPrime(s[leftIndex]) && !IsPrime(s[n - 1]) ? 1 : 0;
        }

        if (memo[leftIndex, k] != -1) return memo[leftIndex, k];

        int result = 0;
        for (int i = leftIndex + minLength; i < n; ++i) {
            if (IsPrime(s[leftIndex]) && !IsPrime(s[i - 1])) {
                result = (result + Dfs(s, i, k - 1, minLength, memo)) % MOD;
            }
        }
        memo[leftIndex, k] = result;
        return result;
    }

    public static int BeautifulPartitions(string s, int k, int minLength) {
        int[,] memo = new int[s.Length, k + 1];
        for(int i = 0; i < s.Length; i++)
            for(int j = 0; j <= k; j++)
                memo[i,j] = -1;
        return Dfs(s, 0, k, minLength, memo);
    }

    public static void Main() {
        string s = "23542185131";
        int k = 3, minLength = 2;
        Console.WriteLine(BeautifulPartitions(s, k, minLength));
    }
}

Python solves partitions recursively with memoization by integrating multilevel function calls to validate unique partitions configurations. Once discovered, such configurations are conserved within a memoization construct, promoting efficient retrieval.

Complexity

The implementation shows O(n^2 * k) time complexity, with space complexity governed by O(n*k) for structured results caching.

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:

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

TypeScript

function beautifulPartitions(s: string, k: number, minLength: number): number {
    const prime = (c: string): boolean => {
        return c === '2' || c === '3' || c === '5' || c === '7';
    };

    const n: number = s.length;
    if (!prime(s[0]) || prime(s[n - 1])) return 0;

    const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
    const g: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
    const mod: number = 1e9 + 7;

    f[0][0] = g[0][0] = 1;

    for (let i = 1; i <= n; ++i) {
        if (i >= minLength && !prime(s[i - 1]) && (i === n || prime(s[i]))) {
            for (let j = 1; j <= k; ++j) {
                f[i][j] = g[i - minLength][j - 1];
            }
        }
        for (let j = 0; j <= k; ++j) {
            g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
        }
    }

    return f[n][k];
}

func beautifulPartitions(s string, k int, minLength int) int {
	prime := func(c byte) bool {
		return c == '2' || c == '3' || c == '5' || c == '7'
	}
	n := len(s)
	if !prime(s[0]) || prime(s[n-1]) {
		return 0
	}
	const mod int = 1e9 + 7
	f := make([][]int, n+1)
	g := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
		g[i] = make([]int, k+1)
	}
	f[0][0], g[0][0] = 1, 1
	for i := 1; i <= n; i++ {
		if i >= minLength && !prime(s[i-1]) && (i == n || prime(s[i])) {
			for j := 1; j <= k; j++ {
				f[i][j] = g[i-minLength][j-1]
			}
		}
		for j := 0; j <= k; j++ {
			g[i][j] = (g[i-1][j] + f[i][j]) % mod
		}
	}
	return f[n][k]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	The time complexity is `O(kn)` and space complexity is `O(n)`, relying on dynamic programming methodologies and array storage.
Recursive with Memoization	The implementation shows `O(n^2 * k)` time complexity, with space complexity governed by `O(n*k)` for structured results caching.
Dynamic Programming	–

Complexity analysis

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

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.

Number of Beautiful Partitions solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Recursive with Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Beautiful Partitions solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Recursive with Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems