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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(nk)
• Space complexity: O(nk)

 

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @param {number} minLength
 * @return {number}
 */
const beautifulPartitions = function (s, k, minLength) {
  const MODULO = 10 ** 9 + 7;
  const n = s.length;
  const primes = new Set(['2', '3', '5', '7']);

  if (!primes.has(s[0]) || primes.has(s[n - 1])) return 0;

  const dp = Array.from({ length: n }, () => new Array(k).fill(-1));

  const getPartitions = (index, parts) => {
    if (index <= n && parts === 0) return 1;

    if (index >= n) return 0;

    if (dp[index][parts] !== -1) return dp[index][parts];

    const isPrevPrime = primes.has(s[index - 1]);
    const isPrime = primes.has(s[index]);
    let result = getPartitions(index + 1, parts);

    if (isPrime && !isPrevPrime) {
      const count = getPartitions(index + minLength, parts - 1);

      result = (result + count) % MODULO;
    }

    dp[index][parts] = result;

    return result;
  };

  return getPartitions(minLength, k - 1);
};