Number of Beautiful Partitions

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<sup>9</sup> + 7.

A substring is a contiguous sequence of characters within a string.

For example:

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"

Input: s = "23542185131", k = 3, minLength = 3 Output: 1 Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".

Input: s = "3312958", k = 3, minLength = 1 Output: 1 Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".

def solve():
    s = input()
    k = int(input())
    minLength = int(input())
    n = len(s)
    mod = 10**9 + 7

    def is_prime(digit):
        return digit in ['2', '3', '5', '7']

    def is_valid_partition(partition):
        if len(partition) != k:
            return False
        
        for sub in partition:
            if len(sub) < minLength:
                return False
            if not is_prime(sub[0]) or is_prime(sub[-1]):
                return False
        return True

    def find_partitions(index, current_partition):
        if len(current_partition) == k - 1:
            remaining_string = s[index:]
            if not remaining_string:
                return 0
            if len(remaining_string) < minLength:
                return 0
            if not is_prime(remaining_string[0]) or is_prime(remaining_string[-1]):
                return 0
            return 1

        count = 0
        for i in range(index + minLength, n - (k - len(current_partition) - 1) * minLength + 1):
            substring = s[index:i]
            if len(substring) >= minLength and is_prime(substring[0]) and not is_prime(substring[-1]):
                count = (count + find_partitions(i, current_partition + [substring])) % mod
        return count

    ans = 0
    for i in range(minLength, n - (k - 1) * minLength + 1):
        first_substring = s[:i]
        if len(first_substring) >= minLength and is_prime(first_substring[0]) and not is_prime(first_substring[-1]):
            ans = (ans + find_partitions(i, [first_substring])) % mod
    print(ans)

# Example Usage (Comment out when submitting to LeetCode or similar):
# s = "23542185131"
# k = 3
# minLength = 2
# solve()

# Dynamic programming solution:
def solve_dp():
    s = input()
    k = int(input())
    minLength = int(input())
    n = len(s)
    mod = 10**9 + 7

    def is_prime(digit):
        return digit in ['2', '3', '5', '7']

    dp = [[0] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 1

    for num_partitions in range(1, k + 1):
        for i in range(num_partitions * minLength, n + 1):
            for j in range(minLength, i + 1):
                if i - j >= 0:
                    substring = s[i-j:i]
                    if is_prime(substring[0]) and not is_prime(substring[-1]):
                        dp[num_partitions][i] = (dp[num_partitions][i] + dp[num_partitions-1][i-j]) % mod

    print(dp[k][n])

# Example Usage (Comment out when submitting to LeetCode or similar):
# s = "23542185131"
# k = 3
# minLength = 2
# solve_dp()

# Example Usage (Comment out when submitting to LeetCode or similar):
# s = "23542185131"
# k = 3
# minLength = 3
# solve_dp()

# Example Usage (Comment out when submitting to LeetCode or similar):
# s = "3312958"
# k = 3
# minLength = 1
# solve_dp()

Explanation:

The problem requires finding the number of beautiful partitions of a given string s into k non-intersecting substrings, where each substring has a length of at least minLength, starts with a prime digit, and ends with a non-prime digit.

1. Brute Force (Recursive) Solution:

The brute force approach involves recursively exploring all possible partitions of the string and checking if each partition is beautiful. This approach has exponential time complexity and is not efficient for larger inputs.

def solve():
    s = input()
    k = int(input())
    minLength = int(input())
    n = len(s)
    mod = 10**9 + 7

    def is_prime(digit):
        return digit in ['2', '3', '5', '7']

    def is_valid_partition(partition):
        if len(partition) != k:
            return False
        
        for sub in partition:
            if len(sub) < minLength:
                return False
            if not is_prime(sub[0]) or is_prime(sub[-1]):
                return False
        return True

    def find_partitions(index, current_partition):
        if len(current_partition) == k - 1:
            remaining_string = s[index:]
            if not remaining_string:
                return 0
            if len(remaining_string) < minLength:
                return 0
            if not is_prime(remaining_string[0]) or is_prime(remaining_string[-1]):
                return 0
            return 1

        count = 0
        for i in range(index + minLength, n - (k - len(current_partition) - 1) * minLength + 1):
            substring = s[index:i]
            if len(substring) >= minLength and is_prime(substring[0]) and not is_prime(substring[-1]):
                count = (count + find_partitions(i, current_partition + [substring])) % mod
        return count

    ans = 0
    for i in range(minLength, n - (k - 1) * minLength + 1):
        first_substring = s[:i]
        if len(first_substring) >= minLength and is_prime(first_substring[0]) and not is_prime(first_substring[-1]):
            ans = (ans + find_partitions(i, [first_substring])) % mod
    print(ans)

2. Optimal (Dynamic Programming) Solution:

A more efficient approach is to use dynamic programming to avoid redundant calculations. We can create a 2D DP table dp[i][j] where dp[i][j] stores the number of beautiful partitions of the first j characters of s into i substrings.

def solve_dp():
    s = input()
    k = int(input())
    minLength = int(input())
    n = len(s)
    mod = 10**9 + 7

    def is_prime(digit):
        return digit in ['2', '3', '5', '7']

    dp = [[0] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 1

    for num_partitions in range(1, k + 1):
        for i in range(num_partitions * minLength, n + 1):
            for j in range(minLength, i + 1):
                if i - j >= 0:
                    substring = s[i-j:i]
                    if is_prime(substring[0]) and not is_prime(substring[-1]):
                        dp[num_partitions][i] = (dp[num_partitions][i] + dp[num_partitions-1][i-j]) % mod

    print(dp[k][n])

Time Complexity Analysis:

• Brute Force: The time complexity is exponential, roughly O(branches^depth), where branches is the number of possibilities for each substring and depth is k. It quickly becomes unusable for larger inputs.
• Dynamic Programming: The time complexity is O(k * n * n), where k is the number of partitions and n is the length of the string. This is because we have a nested loop that iterates through the number of partitions and the length of the string, and another inner loop to consider substring lengths.

Space Complexity Analysis:

• Brute Force: The space complexity is O(k), due to the recursion depth.
• Dynamic Programming: The space complexity is O(k * n), because we use a 2D DP table of size (k+1) x (n+1) to store the intermediate results.

Edge Cases:

1. Empty String: If the input string s is empty, there are no beautiful partitions.
2. k is zero: If k is zero, there are no partitions.
3. minLength is greater than the string length: If minLength is greater than the length of the string, there are no valid substrings.
4. k * minLength is greater than the string length: If the combined minimum length of all partitions exceeds the string length, no valid partitions exist.
5. No valid starting or ending digits: If the string doesn't contain any prime starting digits or non-prime ending digits, no beautiful partitions can be formed.
6. Large Numbers: The number of beautiful partitions can be very large, so it's important to take the modulo 10^9 + 7 to prevent overflow.