# Number of Beautiful Partitions
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-beautiful-partitions)
Canonical: https://scaleengineer.com/dsa/problems/number-of-beautiful-partitions
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## 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** `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'`.

# Approaches
## Top-Down DP (Recursion with Memoization)
This approach uses recursion with memoization, which is a top-down dynamic programming technique. We define a function that solves the problem for a subproblem and use a memoization table to store the results of subproblems to avoid redundant calculations. The state of our recursion is defined by `(i, j)`, representing the starting index of the string suffix to be partitioned and the number of partitions remaining.
**Time:** O(n * k * n). There are `n * k` states, and each state computation involves a loop that can run up to `n` times. · **Space:** O(n * k) for the memoization table and recursion stack depth.
**Pros:** Relatively straightforward to formulate from the problem's recursive nature.; Correctly solves the problem for smaller constraints.
**Cons:** The time complexity of `O(n^2 * k)` is too slow for the given constraints (`n, k <= 1000`) and will result in a Time Limit Exceeded (TLE) error.
### Explanation
The core idea is to define a function, say `solve(i, j)`, which calculates the number of ways to partition the suffix `s[i:]` into `j` beautiful partitions. The final answer is `solve(0, k)`.

To compute `solve(i, j)`, we try to form the first of the `j` partitions. This partition must start at index `i` and end at some index `p`. For this partition `s[i...p]` to be beautiful, it must satisfy three conditions: its length must be at least `minLength`, `s[i]` must be prime, and `s[p]` must be non-prime. If `s[i]` is not prime, `solve(i, j)` is 0. Otherwise, we iterate through all valid `p` and for each, we recursively call `solve(p + 1, j - 1)` to find the number of ways for the rest of the string. The sum of results from these calls gives `solve(i, j)`. 

Without memoization, this would lead to an exponential number of calls. By storing the result of each `solve(i, j)` call in a 2D array `memo`, we ensure that each subproblem is solved only once.

```java
class Solution {
    int n;
    int k;
    int minLength;
    String s;
    int MOD = 1_000_000_007;
    Integer[][] memo;

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

    private int solve(int i, int j) {
        if (j == 0) {
            return i == n ? 1 : 0;
        }
        if (i >= n) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        // The first character of a partition must be prime.
        if (!isPrime(s.charAt(i))) {
            return memo[i][j] = 0;
        }

        long count = 0;
        // Iterate through possible end points 'p' for the current partition.
        for (int p = i + minLength - 1; p < n; p++) {
            // The last character of a partition must be non-prime.
            if (!isPrime(s.charAt(p))) {
                count = (count + solve(p + 1, j - 1)) % MOD;
            }
        }

        return memo[i][j] = (int) count;
    }

    public int beautifulPartitions(String s, int k, int minLength) {
        this.n = s.length();
        this.k = k;
        this.minLength = minLength;
        this.s = s;
        this.memo = new Integer[n + 1][k + 1];
        
        if (!isPrime(s.charAt(0)) || isPrime(s.charAt(n - 1))) {
            return 0;
        }

        return solve(0, k);
    }
}
```
### Algorithm
1. Define a recursive function `solve(i, j)` that computes the number of beautiful partitions for the suffix of the string `s` starting at index `i`, using `j` partitions.
2. **Base Cases:**
   - If `j` is 0, it means we have used all `k` partitions. A valid solution is found only if we have also consumed the entire string (`i == n`). So, return `1` if `i == n`, otherwise `0`.
   - If `i >= n` (we've run out of string) but `j > 0` (still need to make partitions), it's impossible. Return `0`.
3. **Recursive Step:**
   - For a partition to start at index `i`, `s.charAt(i)` must be a prime digit. If not, no beautiful partition can start here, so return `0`.
   - If `s.charAt(i)` is prime, iterate through all possible end positions `p` for the current partition. The end position `p` must satisfy:
     - The partition length `p - i + 1` is at least `minLength`.
     - The character `s.charAt(p)` is a non-prime digit.
   - For each valid end position `p`, we have formed one beautiful partition `s.substring(i, p + 1)`. We then need to partition the rest of the string `s.substring(p + 1)` into `j - 1` partitions. The number of ways to do this is given by the recursive call `solve(p + 1, j - 1)`.
   - Sum up the results from these recursive calls, taking the result modulo `10^9 + 7`.
4. **Memoization:**
   - To avoid recomputing results for the same state `(i, j)`, use a 2D array `memo[n][k+1]` to store the computed values. Before computing `solve(i, j)`, check if it's already in the memoization table.

## Bottom-Up DP with Suffix Sums
This approach uses bottom-up dynamic programming. We build the solution iteratively, starting from smaller subproblems. The key insight is to optimize the transition step. The naive DP transition involves a summation over previous results, leading to `O(n^2 * k)` complexity. By pre-calculating suffix sums for each column of the DP table, we can reduce the transition to `O(1)`, thus improving the overall time complexity.
**Time:** O(n * k). The outer loop runs `k` times. Inside, we compute the suffix sum array in `O(n)` and then fill the current DP column in `O(n)`. Total time is `k * (O(n) + O(n)) = O(n*k)`. · **Space:** O(n * k) to store the entire DP table.
**Pros:** Efficient `O(n*k)` time complexity, which is fast enough for the given constraints.; Systematic bottom-up approach avoids recursion overhead.
**Cons:** The space complexity of `O(n*k)` might be large, although it fits within typical memory limits for the given constraints.
### Explanation
Let `dp[i][j]` be the number of ways to partition the suffix `s[i...n-1]` into `j` beautiful partitions. Our goal is to find `dp[0][k]`. The base case is `dp[n][0] = 1`, as there's one way to partition an empty string into zero parts.

We iterate from `j = 1` to `k`. For each `j`, we want to compute `dp[i][j]` for all `i`. A partition starting at `i` must have `s[i]` as a prime digit. If so, `dp[i][j]` is the sum of `dp[p+1][j-1]` for all valid end points `p`. A point `p` is a valid end if `p >= i + minLength - 1` and `s[p]` is non-prime.

The crucial optimization is to avoid re-calculating this sum for every `(i, j)`. For a fixed `j`, the sum `sum_{p=q}^{n-1, s[p] is non-prime} dp[p+1][j-1]` can be pre-calculated for all `q` in `O(n)` time. Let's call this `suffixSum[q]`. We can compute it by iterating `q` from `n-1` down to `0`. Then, `dp[i][j]` is simply `suffixSum[i + minLength - 1]`. This reduces the complexity of each state's computation from `O(n)` to `O(1)`.

```java
class Solution {
    private boolean isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    public int beautifulPartitions(String s, int k, int minLength) {
        int n = s.length();
        int MOD = 1_000_000_007;

        if (!isPrime(s.charAt(0)) || isPrime(s.charAt(n - 1))) {
            return 0;
        }

        long[][] dp = new long[n + 1][k + 1];
        dp[n][0] = 1;

        for (int j = 1; j <= k; j++) {
            long[] suffixSum = new long[n + 1];
            for (int p = n - 1; p >= 0; p--) {
                suffixSum[p] = suffixSum[p + 1];
                if (!isPrime(s.charAt(p))) {
                    suffixSum[p] = (suffixSum[p] + dp[p + 1][j - 1]) % MOD;
                }
            }

            for (int i = n - 1; i >= 0; i--) {
                if (isPrime(s.charAt(i)) && i + minLength <= n) {
                    dp[i][j] = suffixSum[i + minLength - 1];
                }
            }
        }

        return (int) dp[0][k];
    }
}
```
### Algorithm
1. Define a 2D DP array `dp[i][j]`, where `dp[i][j]` stores the number of beautiful partitions of the suffix `s[i...n-1]` into `j` parts.
2. **Base Case:** `dp[n][0] = 1`. This signifies that an empty suffix (`s[n...n-1]`) can be partitioned into 0 parts in one way.
3. **Iteration:** We fill the DP table column by column, for `j` from 1 to `k`. For each `j`, we iterate `i` from `n-1` down to `0`.
4. **Transition:** The recurrence relation is `dp[i][j] = sum(dp[p+1][j-1])` over all valid split points `p`. A split point `p` is valid if `s[i]` is prime, `s[p]` is non-prime, and the partition length is at least `minLength`.
5. **Optimization:** The summation `sum(dp[p+1][j-1])` where `s[p]` is non-prime can be computed efficiently. For each column `j`, we first precompute a `suffixSum` array based on the values from column `j-1`. `suffixSum[q]` will store `sum_{p=q}^{n-1, s[p] is non-prime} dp[p+1][j-1]`.
6. This `suffixSum` array is computed in `O(n)` by iterating `p` from `n-1` down to `0`. The relation is `suffixSum[p] = suffixSum[p+1]`, and if `s[p]` is non-prime, we add `dp[p+1][j-1]`.
7. With the `suffixSum` array, `dp[i][j]` can be found in `O(1)`: `dp[i][j] = suffixSum[i + minLength - 1]` (if `s[i]` is prime and other conditions met).
8. **Final Answer:** The result is `dp[0][k]`.

## Space-Optimized Bottom-Up DP
This is the most optimized approach, improving upon the previous bottom-up DP solution by reducing its space complexity. We notice that the computation for the number of partitions `j` only depends on the results for `j-1` partitions. This dependency allows us to discard older columns of the DP table that are no longer needed, significantly saving space.
**Time:** O(n * k). The time complexity remains the same as the previous approach, as the number of computations is unchanged. · **Space:** O(n). We use a few arrays of size `n+1`, but their usage is not dependent on `k`.
**Pros:** Optimal time complexity of `O(n*k)`.; Optimal space complexity of `O(n)`.
**Cons:** The logic can be slightly more complex to manage due to the array swapping/updating.
### Explanation
The logic is identical to the standard bottom-up DP approach, but we optimize memory usage. Instead of a 2D `dp` table of size `(n+1) x (k+1)`, we maintain only two 1D arrays: `prev_dp` to hold the results for `j-1` partitions, and `dp` to compute the results for `j` partitions. 

In each iteration of the main loop over `j`, we treat `prev_dp` as read-only to compute the `suffixSum` and then the new `dp` array. Once the `dp` array for the current `j` is fully computed, it becomes the `prev_dp` for the next iteration `j+1`. This cycle continues until `j=k`. The final answer is stored in `prev_dp[0]` after the loop finishes.

```java
class Solution {
    private boolean isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    public int beautifulPartitions(String s, int k, int minLength) {
        int n = s.length();
        int MOD = 1_000_000_007;

        if (!isPrime(s.charAt(0)) || isPrime(s.charAt(n - 1))) {
            return 0;
        }

        long[] prev_dp = new long[n + 1];
        prev_dp[n] = 1;

        for (int j = 1; j <= k; j++) {
            long[] dp = new long[n + 1];
            long[] suffixSum = new long[n + 1];
            
            for (int p = n - 1; p >= 0; p--) {
                suffixSum[p] = suffixSum[p + 1];
                if (!isPrime(s.charAt(p))) {
                    suffixSum[p] = (suffixSum[p] + prev_dp[p + 1]) % MOD;
                }
            }

            for (int i = n - 1; i >= 0; i--) {
                if (isPrime(s.charAt(i)) && i + minLength <= n) {
                    dp[i] = suffixSum[i + minLength - 1];
                }
            }
            prev_dp = dp;
        }

        return (int) prev_dp[0];
    }
}
```
### Algorithm
1. This approach builds upon the previous bottom-up DP method.
2. Observe that to compute the values for `dp[...][j]` (the `j`-th column), we only need the values from `dp[...][j-1]` (the `j-1`-th column).
3. Instead of a full `O(n*k)` DP table, we can use just two 1D arrays: `dp` of size `n+1` for the current column `j`, and `prev_dp` of size `n+1` for the previous column `j-1`.
4. **Initialization:** `prev_dp` is initialized for `j=0`. `prev_dp[n] = 1`, and all other elements are 0.
5. **Iteration:** Loop `j` from 1 to `k`.
   - Inside the loop, create a new array `dp` for the current column `j`.
   - Compute the `suffixSum` array based on `prev_dp` (values from column `j-1`), just like in the previous approach.
   - Fill the `dp` array using the `suffixSum` array.
   - After computing all values for column `j`, update `prev_dp` to be `dp` for the next iteration.
6. **Final Answer:** After the loops complete, the answer is `prev_dp[0]`.

# Solutions
### Java

```java
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int beautifulPartitions ( String s , int k , int minLength ) { int n = s . length (); if (! prime ( s . charAt ( 0 )) || prime ( s . charAt ( n - 1 ))) { return 0 ; } int [][] f = new int [ n + 1 ][ k + 1 ]; int [][] g = new int [ n + 1 ][ k + 1 ]; f [ 0 ][ 0 ] = 1 ; g [ 0 ][ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( i >= minLength && ! prime ( s . charAt ( i - 1 )) && ( i == n || prime ( s . charAt ( i )))) { for ( int j = 1 ; j <= k ; ++ j ) { f [ i ][ j ] = g [ i - minLength ][ j - 1 ]; } } for ( int j = 0 ; j <= k ; ++ j ) { g [ i ][ j ] = ( g [ i - 1 ][ j ] + f [ i ][ j ]) % MOD ; } } return f [ n ][ k ]; } private boolean prime ( char c ) { return c == '2' || c == '3' || c == '5' || c == '7' ; } }
```

### CPP

```cpp
class Solution { public: const int mod = 1e9 + 7 ; int beautifulPartitions ( string s , int k , int minLength ) { int n = s . size (); auto prime = []( char c ) { return c == '2' || c == '3' || c == '5' || c == '7' ; }; if ( ! prime ( s [ 0 ]) || prime ( s [ n - 1 ])) return 0 ; vector < vector < int >> f ( n + 1 , vector < int > ( k + 1 )); vector < vector < int >> g ( n + 1 , vector < int > ( k + 1 )); f [ 0 ][ 0 ] = g [ 0 ][ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( i >= minLength && ! prime ( s [ i - 1 ]) && ( i == n || prime ( s [ i ]))) { for ( int j = 1 ; j <= k ; ++ j ) { f [ i ][ j ] = g [ i - minLength ][ j - 1 ]; } } for ( int j = 0 ; j <= k ; ++ j ) { g [ i ][ j ] = ( g [ i - 1 ][ j ] + f [ i ][ j ]) % mod ; } } return f [ n ][ k ]; } };
```

### Python

```python
class Solution : def beautifulPartitions ( self , s : str , k : int , minLength : int ) -> int : primes = '2357' if s [ 0 ] not in primes or s [ - 1 ] in primes : return 0 mod = 10 ** 9 + 7 n = len ( s ) f = [[ 0 ] * ( k + 1 ) for _ in range ( n + 1 )] g = [[ 0 ] * ( k + 1 ) for _ in range ( n + 1 )] f [ 0 ][ 0 ] = g [ 0 ][ 0 ] = 1 for i , c in enumerate ( s , 1 ): if i >= minLength and c not in primes and ( i == n or s [ i ] in primes ): for j in range ( 1 , k + 1 ): f [ i ][ j ] = g [ i - minLength ][ j - 1 ] for j in range ( k + 1 ): g [ i ][ j ] = ( g [ i - 1 ][ j ] + f [ i ][ j ]) % mod return f [ n ][ k ]
```