2478. Number of Beautiful Partitions

Description

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

Solutions

Solution 1: 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 \(i\)th character can be the last character of the \(j\)th section, it needs to meet the following conditions simultaneously:

The \(i\)th character is a non-prime number;
The \(i+1\)th character is a prime number, or the \(i\)th character is the last character of the entire string.

If the \(i\)th character cannot be the last character of the \(j\)th 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.

Python3JavaC++GoTypeScript

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]

class Solution {
    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;
        final int mod = (int) 1e9 + 7;
        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';
    }
}

class Solution {
public:
    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;
        const int mod = 1e9 + 7;
        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];
    }
};

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]
}

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];
}

2478. Number of Beautiful Partitions

Description

Solutions

Solution 1: Dynamic Programming

Comments