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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Beautiful Partitions

Number: 2569

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a string s consisting of the digits '1' to '9', and two integers k and minLength, count the number of ways to partition s into exactly k non-overlapping substrings such that:

  • Each substring has length at least minLength.
  • Each substring starts with a prime digit—'2', '3', '5', or '7'.
  • Each substring ends with a non-prime digit. Return the count modulo 10^9 + 7.

Key Insights

  • Use dynamic programming (DP) to count the ways to break the string into valid segments.
  • Define the state as dp[i][p] representing the number of ways to partition the prefix ending at index i with p valid partitions.
  • Transition: From a valid starting index i, consider every possible ending index j such that the substring s[i...j-1] has length at least minLength and meets the start (prime) and end (non-prime) conditions.
  • Iterate over possible partition boundaries and build the DP solution.
  • Modulo arithmetic is necessary to keep numbers manageable.
  • The constraints (s.length up to 1000) allow an O(n^2 * k) solution in the worst case.

Space and Time Complexity

Time Complexity: O(n^2 * k), where n is the length of the string. This is because for each of up to n positions we check potential end positions over the next substring. Space Complexity: O(n * k) for the DP table.

Solution

We solve the problem using a 2D DP approach. Let dp[i][p] be the number of ways to partition the first i characters of s into p valid segments. We initialize dp[0][0]=1 (an empty prefix with 0 segments). For each index i and segment count p, we try to extend a valid segment from i to j (with j-i >= minLength) only if s[i] is a prime digit and s[j-1] is a non-prime digit. Then we add dp[i][p] to dp[j][p+1]. Finally, dp[n][k] will be our answer modulo 10^9+7. Care must be taken to only consider valid partition boundaries and ensure that the conditions hold for every segment.

Data structures used:

  • A 2D list/array dp to memoize partition counts.
  • Use of modulus arithmetic to keep results within bounds.

Algorithmic steps:

  1. Check if the first digit is prime and the last digit is non-prime; if not, return 0 early.
  2. Initialize the DP table: dp[0][0] = 1.
  3. Loop through all possible starting indices and partition counts, then iterate through potential ending indices that satisfy the minimum length.
  4. Validate the substring’s starting and ending digits.
  5. Update the DP table with the current count.
  6. Return dp[n][k] modulo (10^9+7).

Code Solutions

# Python solution for Number of Beautiful Partitions

MOD = 10**9 + 7

def beautifulPartitions(s: str, k: int, minLength: int) -> int:
    n = len(s)
    # Define prime digits as a set for constant time lookup.
    is_prime_digit = {'2', '3', '5', '7'}
    
    # Early validation: first char must be prime and last must be non-prime.
    if s[0] not in is_prime_digit or s[-1] in is_prime_digit:
        return 0
    
    # Initialize dp table with 0s. dp[i][p] = ways to partition s[0:i] into p segments.
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # base case: empty prefix with 0 partitions.
    
    # Loop over the starting position of segments.
    for i in range(n):
        for p in range(k):
            # If no way to partition s[0:i] into p parts, skip.
            if dp[i][p] == 0:
                continue
            # Check if the current segment can start a new partition.
            if s[i] not in is_prime_digit:
                continue
            # Try all possible end indices j for the current segment.
            # j is the end index (1-indexed for dp array slicing) where j - i >= minLength.
            for j in range(i + minLength, n + 1):
                # Only consider partition if the last character of this segment is non-prime.
                if s[j-1] in is_prime_digit:
                    continue
                # For partitions other than the last segment, we need to ensure that 
                # there is a possibility to start a new segment from j with a prime digit.
                if p < k - 1 and j < n and s[j] not in is_prime_digit:
                    continue
                # Valid partition, update dp.
                dp[j][p+1] = (dp[j][p+1] + dp[i][p]) % MOD
    return dp[n][k]

# Example test run
print(beautifulPartitions("23542185131", 3, 2))  # Expected output: 3
← Back to All Questions