We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Beautiful Partitions

Difficulty: Hard

Problem 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^9 + 7.

Key Insights

  • The problem involves partitioning a string based on specific rules regarding starting and ending digits.
  • Dynamic programming can be used to efficiently count valid partitions.
  • Identifying prime and non-prime digits is essential for determining valid substrings.
  • The minimum length constraint ensures that partitions cannot be arbitrarily small.

Space and Time Complexity

Time Complexity: O(n^2 * k) - where n is the length of the string and k is the number of partitions. Space Complexity: O(k) - for storing the results of subproblems in dynamic programming.

Solution

To solve the problem, we can use a dynamic programming approach. We define a DP table where dp[i][j] represents the number of ways to partition the first i characters of the string into j beautiful partitions.

  1. Iterate through the string to identify valid starting and ending positions for substrings based on prime and non-prime digits.
  2. For each valid partition point, update the DP table by adding the number of ways to split at that point.
  3. Ensure that each partition meets the minimum length requirement.
  4. The final answer will be stored in dp[n][k], where n is the length of the string.

Code Solutions

def is_prime(digit):
    return digit in '2357'

def beautiful_partitions(s, k, minLength):
    MOD = 10**9 + 7
    n = len(s)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # Base case: 1 way to partition an empty string into 0 parts

    # Iterate through each position in the string
    for j in range(1, k + 1):
        for i in range(1, n + 1):
            for start in range(max(0, i - minLength), i):
                if is_prime(s[start]) and not is_prime(s[i - 1]):
                    dp[i][j] = (dp[i][j] + dp[start][j - 1]) % MOD

    return dp[n][k]

# Example usage
print(beautiful_partitions("23542185131", 3, 2))  # Output: 3
← Back to All Questions