2478. Number of Beautiful Partitions

Problem Description

This problem involves devising an algorithm to count how many ways you can divide a string s into k non-overlapping substrings, where each substring adheres to specific conditions involving their lengths and the digits they start and end with. The string s is composed of digits '1' through '9', and the problem specifies additional constraints as follows:

• The string must be partitioned into k non-intersecting (non-overlapping) substrings.
• Each resulting substring must be at least minLength characters long.
• Each substring must start with a prime digit (2, 3, 5, or 7) and end with a non-prime digit.

The objective is to determine the count of all possible "beautiful partitions" of the string s. Due to the potential for a very large number, the result must be returned modulo 10^9 + 7.

A substring should be understood as a sequence of characters that are in consecutive order within the original string s.

Intuition

The problem at hand is a dynamic programming challenge. The intuition for such problems generally comes from realizing that the solution for a bigger problem depends on the solution of its sub-problems. Here, we specifically want to find the number of ways to split the string into k "beautiful" parts, which will depend on the number of ways to make j parts with a subset of the string, where j < k.

The solution approach uses two auxiliary two-dimensional arrays (let's call them f and g) to keep track of the number of ways to partition substrings of s into j beautiful partitions upto a certain index i.

• f[i][j] denotes the number of ways we can partition the string upto the i-th character resulting in exactly j partitions where the j-th partition ends at position i.
• g[i][j] is used to track the running total sum of f[i][j] upto that point.

The algorithm incrementally constructs these arrays by iterating over the characters of the string s and using the following logic:

1. Initialize both f[0][0] and g[0][0] to 1, as there is one way to partition an empty string into 0 parts.
2. At each character, i, check if a "beautiful" partition could end at this character; that is, the current character must not be a prime, and if we go back minLength characters, we should start with a prime (also taking into account edge cases at the ends of the string).
3. If the current character can be the end of a "beautiful" partition, update f by using the value from g that tracks the number of ways we could have made j-1 partitions up to this point (since we are potentially adding one more partition here).
4. Update g by summing the current values in g and f for this index, taking care to apply the modulo 10^9 + 7.

The final answer is the value of f[n][k], as it represents the number of ways to partition the entire string into k beautiful partitions.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements dynamic programming to count the number of "beautiful" partitions. Let's walk through the critical parts of the implementation:

1. Initializing Arrays: Two-dimensional arrays f and g are created of size n + 1 by k + 1, where n is the length of the string s. These arrays are initialized to zero but with f[0][0] = g[0][0] = 1, because there's exactly one way to partition a string of length 0 into 0 parts.

2. Dynamic Programming Loop:

   • Loop through the string s while also keeping track of the current position i (1-indexed).

   • Check if the current character c can be the ending of a "beautiful" partition by ensuring that: a. The substring has at least minLength characters, which means i should be greater than or equal to minLength. b. The character must be non-prime. c. Either we're at the end of the string or the next character is prime.

   • If the substring can end at this character, then for each possible partition count j (from 1 to k),

     • We calculate f[i][j] by looking at g[i - minLength][j - 1], indicating the number of ways to form j-1 partitions ending before we reach a minLength distance from the current index.

3. Accumulating Results:

   • The array g accumulates the counts of valid partitions. For every index i and for every number of partitions j, we add the number of ways to extend the existing j partitions (f[i][j]) to the sum up to the previous character (g[i - 1][j]), ensuring that we carry the count forward and also apply the modulo 10^9 + 7 to keep the number within the range.

4. Returning the Result:

   • The final result is the value at f[n][k], indicating the number of ways the entire string of length n can be partitioned into k "beautiful" partitions.

The used data structures here are primarily arrays for dynamic programming. The algorithm itself is a standard dynamic programming pattern, which involves breaking down the problem into smaller subproblems (counting the partitions that can end at each index for a given number of partitions), solving each subproblem (with the loop), and building up to the solution of the overall problem (using the results of subproblems).

Overall, the implementation is efficient as it only requires a single pass through the string and has a time complexity that is linear with respect to the size of the string and the number of partitions, which is O(n * k).

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have the string s = "23542" and we want to find out the number of ways to divide this string into k = 2 non-overlapping substrings with each substring having a minimum length of minLength = 2, starting with a prime digit, and ending with a non-prime digit.

Let's walk through the dynamic programming approach step by step.

1. Initializing Arrays: We initialize our arrays f and g with dimensions [6][3] because our string length n is 5 (s.length + 1) and k is 2 (+1 is to include zero partitions). Set all values to 0, except f[0][0] and g[0][0], which are set to 1.

1f = [ [1, 0, 0],
2      [0, 0, 0],
3      [0, 0, 0], 
4      [0, 0, 0],
5      [0, 0, 0],
6      [0, 0, 0] ]
7    
8g = [ [1, 0, 0],
9      [0, 0, 0],
10      [0, 0, 0], 
11      [0, 0, 0],
12      [0, 0, 0],
13      [0, 0, 0] ]

2. Dynamic Programming Loop:

   • We loop from i = 1 to i = 5, as our string has 5 characters.
   • We check if a "beautiful" substring can end at each i:
     • For i = 1 and i = 2, no "beautiful" partition can end as we need at least a substring of length 2.
     • At i = 3, we have "235", which ends with a "5" (prime) so it cannot be a "beautiful" partition.
     • At i = 4, we have "35" (string[2,3]), which is a valid partition; it starts with "3" (prime) and ends with "5" (non-prime). We set f[4][1] = g[2][0], which is 1.
     • There's no other valid partition at i = 4 since we need to have at least 2 characters in each substring and we are also counting only the partitions which end exactly at the current step.

3. Accumulating Results:

   • We update our arrays with the new information:

1f = [ [1, 0, 0],
2      [0, 0, 0],
3      [0, 0, 0], 
4      [0, 1, 0],
5      [0, 0, 0],
6      [0, 0, 0] ]
7    
8g = [ [1, 0, 0],
9      [1, 0, 0],
10      [1, 0, 0], 
11      [1, 1, 0],
12      [1, 1, 0],
13      [1, 1, 0] ]

• For i = 5, the substring is "542" which is invalid because it starts with "5" (prime), but "42" (string[3,4]) is validated for the second partition. We set f[5][2] = g[3][1], which is also 1.

4. Returning the Result:
   • Finally, we find that f[5][2] is 1, which means there is exactly one way to partition the string "23542" into 2 "beautiful" substrings according to the conditions.
   • The result, therefore, is 1 modulo 10^9 + 7, which is still 1 since it's under the modulo.

In our dynamic arrays:

1f = [ [1, 0, 0],
2      [0, 0, 0],
3      [0, 0, 0], 
4      [0, 1, 0],
5      [0, 0, 0],
6      [0, 0, 1] ]

f[n][k] holds the final answer, which is f[5][2] = 1. So there is one beautiful partition of the string "23542" when split into 2 substrings.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n * k). Here’s why:

• The main operation occurs within a double nested loop - the outer loop runs for each character in the input string s (with n being the length of s) and the inner loop runs for k + 1 times.
• Within the inner loop, each operation is constant time, where we simply check conditions and update the values of f[i][j] and g[i][j].
• Since these loops are nested, the total number of operations is the product of the number of iterations of each loop (n times for the outer loop, and k + 1 times for the inner loop), which simplifies to O(n * k).

Space Complexity

The space complexity of the given code is O(n * k). Here's the breakdown:

• Two 2D arrays f and g are allocated with dimensions (n + 1) * (k + 1). Each array holds n + 1 rows and k + 1 columns of integer values, which means they each require O(n * k) space.
• Other than the arrays, only a fixed number of integer variables are used, which do not significantly impact the overall space complexity.
• Thus, the dominant factor for space is the size of the 2D arrays, which results in a space complexity of O(n * k).

Learn more about how to find time and space complexity quickly using problem constraints.