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

Solution (Java)

class Solution {
    private final static int MOD = 1_000_000_007;

    public int beautifulPartitions(String s, int k, int minLength) {
        int n = s.length();
        if (!isPrime(s.charAt(0)) || isPrime(s.charAt(n - 1))) return 0;

        int[][] dp = new int[k][n];
        Arrays.fill(dp[0], 1);
        for (int i = 1; i < k; i++) {
            for (int j = 1; j < n; j++) {
                if (j - 0 >= minLength && n - j >= minLength 
                    && !isPrime(s.charAt(j - 1)) && isPrime(s.charAt(j))) {
                    // can cut here.
                    // dp[i][j] = no cut + cut.
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - minLength]) % MOD;
                } else {
                    dp[i][j] = dp[i][j - 1];    // no cut here.
                }
            }
        }

        return dp[k - 1][n - 1];
    }

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

Solution (Javascript)

/**
 * @param {string} s
 * @param {number} k
 * @param {number} minLength
 * @return {number}
 */
var beautifulPartitions = function(s, k, minLength) {
  let n = s.length, nonPrimeIndexes = [];
  for (let i = 0; i < n; i++) {
    if (!isPrime(s[i])) nonPrimeIndexes.push(i);
  }
  let memo = Array(n).fill(0).map(() => Array(k + 1).fill(-1)), MOD = 10 ** 9 + 7;
  return dp(0, k);

  function dp(i, k) {
    let remainingLen = n - i;
    if (remainingLen < Math.max(2, minLength) * k) return 0;
    if (i === n) return k === 0 ? 1 : 0;
    if (k === 0) return 0;
    if (memo[i][k] !== -1) return memo[i][k];

    if (!isPrime(s[i])) return 0;

    let ways = 0;
    let index = binarySearch(i + minLength - 1);
    for (let j = index; j < nonPrimeIndexes.length; j++) {
      ways = (ways + dp(nonPrimeIndexes[j] + 1, k - 1)) % MOD;
    }
    return memo[i][k] = ways;
  }  

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

  function binarySearch(min) { // binary search for the smallest index in nonPrimeIndexes where nonPrimeIndexes[index] >= min
    let low = 0, high = nonPrimeIndexes.length - 1;
    while (low < high) {
      let mid = Math.floor((low + high) / 2);
      if (nonPrimeIndexes[mid] >= min) high = mid;
      else low = mid + 1;
    }
    return nonPrimeIndexes[low] < min ? nonPrimeIndexes.length : low;
  }
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).