Number of Beautiful Partitions

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 ofbeautiful partitions of _s. Since the answer may be very large, return it modulo 10^9 + 7.

A substring is a contiguous sequence of characters within a string.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10



    
    
    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

1
2
3
4
5
6
7



    
    
    Input: s = "23542185131", k = 3, minLength = 3
    Output: 1
    Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".
    

Example 3

1
2
3
4
5
6
7



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

Solution

Method 1 – Dynamic Programming

Intuition

We need to partition s into k substrings, each of at least minLength, starting with a prime digit and ending with a non-prime digit. Use DP: dp[i][j] = number of ways to partition s[0..i] into j beautiful substrings.

Approach

Define is_prime(d) for digits.
Use dp[i][j]: number of ways to partition s[0..i] into j beautiful substrings.
For each possible partition, check if substring starts with prime and ends with non-prime, and length >= minLength.
Use prefix sums for optimization.
Return dp[n][k].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <vector>
#include <string>
using namespace std;
const int MOD = 1e9+7;
class Solution {
public:
    bool is_prime(char c) { return c=='2'||c=='3'||c=='5'||c=='7'; }
    int beautifulPartitions(string s, int k, int minLength) {
        int n = s.size();
        if (!is_prime(s[0]) || is_prime(s[n-1])) return 0;
        vector<vector<int>> dp(n+1, vector<int>(k+1));
        dp[0][0] = 1;
        for (int j = 1; j <= k; ++j) {
            vector<int> pre(n+1);
            for (int i = 0; i <= n; ++i) pre[i] = dp[i][j-1];
            for (int i = minLength; i <= n; ++i) {
                if (is_prime(s[i-minLength]) && !is_prime(s[i-1])) {
                    dp[i][j] = (dp[i][j] + pre[i-minLength]) % MOD;
                }
            }
        }
        return dp[n][k];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public int beautifulPartitions(String s, int k, int minLength) {
        int n = s.length(), MOD = (int)1e9+7;
        if (!isPrime(s.charAt(0)) || isPrime(s.charAt(n-1))) return 0;
        int[][] dp = new int[n+1][k+1];
        dp[0][0] = 1;
        for (int j = 1; j <= k; ++j) {
            int[] pre = new int[n+1];
            for (int i = 0; i <= n; ++i) pre[i] = dp[i][j-1];
            for (int i = minLength; i <= n; ++i) {
                if (isPrime(s.charAt(i-minLength)) && !isPrime(s.charAt(i-1))) {
                    dp[i][j] = (dp[i][j] + pre[i-minLength]) % MOD;
                }
            }
        }
        return dp[n][k];
    }
    boolean isPrime(char c) { return c=='2'||c=='3'||c=='5'||c=='7'; }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    fun beautifulPartitions(s: String, k: Int, minLength: Int): Int {
        val n = s.length; val MOD = 1_000_000_007
        fun isPrime(c: Char) = c=='2'||c=='3'||c=='5'||c=='7'
        if (!isPrime(s[0]) || isPrime(s[n-1])) return 0
        val dp = Array(n+1) { IntArray(k+1) }
        dp[0][0] = 1
        for (j in 1..k) {
            val pre = IntArray(n+1) { dp[it][j-1] }
            for (i in minLength..n) {
                if (isPrime(s[i-minLength]) && !isPrime(s[i-1])) {
                    dp[i][j] = (dp[i][j] + pre[i-minLength]) % MOD
                }
            }
        }
        return dp[n][k]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        MOD = 10**9+7
        n = len(s)
        def is_prime(c): return c in '2357'
        if not is_prime(s[0]) or is_prime(s[-1]): return 0
        dp = [[0]*(k+1) for _ in range(n+1)]
        dp[0][0] = 1
        for j in range(1, k+1):
            pre = [dp[i][j-1] for i in range(n+1)]
            for i in range(minLength, n+1):
                if is_prime(s[i-minLength]) and not is_prime(s[i-1]):
                    dp[i][j] = (dp[i][j] + pre[i-minLength]) % MOD
        return dp[n][k]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
    pub fn beautiful_partitions(s: String, k: i32, min_length: i32) -> i32 {
        let n = s.len(); let k = k as usize; let min_length = min_length as usize;
        let s = s.as_bytes();
        fn is_prime(c: u8) -> bool { matches!(c, b'2'|b'3'|b'5'|b'7') }
        if !is_prime(s[0]) || is_prime(s[n-1]) { return 0; }
        let mut dp = vec![vec![0; k+1]; n+1];
        dp[0][0] = 1;
        for j in 1..=k {
            let pre: Vec<_> = dp.iter().map(|row| row[j-1]).collect();
            for i in min_length..=n {
                if is_prime(s[i-min_length]) && !is_prime(s[i-1]) {
                    dp[i][j] = (dp[i][j] + pre[i-min_length]) % 1_000_000_007;
                }
            }
        }
        dp[n][k]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


function beautifulPartitions(s: string, k: number, minLength: number): number {
    const MOD = 1e9+7, n = s.length;
    const isPrime = (c: string) => '2357'.includes(c);
    if (!isPrime(s[0]) || isPrime(s[n-1])) return 0;
    const dp = Array.from({length: n+1}, () => Array(k+1).fill(0));
    dp[0][0] = 1;
    for (let j = 1; j <= k; ++j) {
        const pre = dp.map(row => row[j-1]);
        for (let i = minLength; i <= n; ++i) {
            if (isPrime(s[i-minLength]) && !isPrime(s[i-1])) {
                dp[i][j] = (dp[i][j] + pre[i-minLength]) % MOD;
            }
        }
    }
    return dp[n][k];
}

Complexity

⏰ Time complexity: O(nk)
🧺 Space complexity: O(nk)

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#