2478

2478. Number of Beautiful Partitions (Hard)

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

Companies: Google

Related Topics:
String, Dynamic Programming

Similar Questions:

• Restore The Array (Hard)
• Number of Ways to Separate Numbers (Hard)

Solution 1. DP

Let dp[k][i+1] be the number of k-partitions using A[0..i] (A[i] must be non-prime).

dp[k][i+1] = sum( dp[k-1][j] | A[j] is prime, 0 <= j <= i - minLen + 1 )
dp[0][0] = 1

The answer is dp[K][N].

Since dp[k][i+1] only depends on the values in the previous row, we can reduce the space complexity from O(KN) to O(N).

// OJ: https://leetcode.com/problems/number-of-beautiful-partitions
// Author: github.com/lzl124631x
// Time: O(KN)
// Space: O(N)
class Solution {
    bool isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }
public:
    int beautifulPartitions(string s, int K, int minLen) {
        long N = s.size(), mod = 1e9 + 7;
        vector<long> dp(N + 1);
        dp[0] = 1;
        for (int k = 1; k <= K; ++k) {
            vector<long> next(N + 1);
            long sum = 0;
            for (int i = 0; i < N; ++i) {
                if (i - minLen + 1 >= 0 && isPrime(s[i - minLen + 1])) sum = (sum + dp[i - minLen + 1]) % mod;
                if (!isPrime(s[i])) {
                    next[i + 1] = (next[i + 1] + sum) % mod;
                }
            }
            swap(dp, next);
        }
        return dp[N];
    }
};