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 thei-th
character resulting in exactlyj
partitions where thej-th
partition ends at positioni
.g[i][j]
is used to track the running total sum off[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:
- Initialize both
f[0][0]
andg[0][0]
to 1, as there is one way to partition an empty string into 0 parts. - 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 backminLength
characters, we should start with a prime (also taking into account edge cases at the ends of the string). - If the current character can be the end of a "beautiful" partition, update
f
by using the value fromg
that tracks the number of ways we could have madej-1
partitions up to this point (since we are potentially adding one more partition here). - Update
g
by summing the current values ing
andf
for this index, taking care to apply the modulo10^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:
-
Initializing Arrays: Two-dimensional arrays
f
andg
are created of sizen + 1
byk + 1
, wheren
is the length of the strings
. These arrays are initialized to zero but withf[0][0] = g[0][0] = 1
, because there's exactly one way to partition a string of length 0 into 0 parts. -
Dynamic Programming Loop:
-
Loop through the string
s
while also keeping track of the current positioni
(1-indexed). -
Check if the current character
c
can be the ending of a "beautiful" partition by ensuring that: a. The substring has at leastminLength
characters, which meansi
should be greater than or equal tominLength
. 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 tok
),- We calculate
f[i][j]
by looking atg[i - minLength][j - 1]
, indicating the number of ways to formj-1
partitions ending before we reach aminLength
distance from the current index.
- We calculate
-
-
Accumulating Results:
- The array
g
accumulates the counts of valid partitions. For every indexi
and for every number of partitionsj
, we add the number of ways to extend the existingj
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 modulo10^9 + 7
to keep the number within the range.
- The array
-
Returning the Result:
- The final result is the value at
f[n][k]
, indicating the number of ways the entire string of lengthn
can be partitioned intok
"beautiful" partitions.
- The final result is the value at
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).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
- Initializing Arrays: We initialize our arrays
f
andg
with dimensions [6][3] because our string lengthn
is 5 (s.length + 1
) andk
is 2 (+1 is to include zero partitions). Set all values to 0, exceptf[0][0]
andg[0][0]
, which are set to 1.
f = [ [1, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0] ] g = [ [1, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0] ]
-
Dynamic Programming Loop:
- We loop from
i = 1
toi = 5
, as our string has 5 characters. - We check if a "beautiful" substring can end at each
i
:- For
i = 1
andi = 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 setf[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.
- For
- We loop from
-
Accumulating Results:
- We update our arrays with the new information:
f = [ [1, 0, 0], [0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0], [0, 0, 0] ] g = [ [1, 0, 0], [1, 0, 0], [1, 0, 0], [1, 1, 0], [1, 1, 0], [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 setf[5][2] = g[3][1]
, which is also 1.
- 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.
- Finally, we find that
In our dynamic arrays:
f = [ [1, 0, 0], [0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0], [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
1class Solution:
2 def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
3 # Define primes as a string containing prime digits
4 prime_digits = '2357'
5
6 # If the first character of the given string is not a prime digit or
7 # the last character is a prime digit, then return 0
8 # as it cannot form a beautiful partition
9 if s[0] not in prime_digits or s[-1] in prime_digits:
10 return 0
11
12 # Define the modulus value for large numbers to prevent overflow
13 mod = 10**9 + 7
14
15 # Calculate the length of the string
16 n = len(s)
17
18 # Initialize two 2D arrays, f and g, to store intermediate results
19 # f[i][j] is the count of beautiful partitions of length exactly i using j partitions
20 # g[i][j] includes f[i][j] and also counts partitions ending before i
21 f = [[0] * (k + 1) for _ in range(n + 1)]
22 g = [[0] * (k + 1) for _ in range(n + 1)]
23
24 # Base case: there's 1 way to divide an empty string using 0 partitions
25 f[0][0] = g[0][0] = 1
26
27 # Loop through characters in the string, indexed from 1 for convenience
28 for i, char in enumerate(s, 1):
29 # Check if the current position can possibly end a partition by checking
30 # - it's at least minLength
31 # - it's a non-prime digit
32 # - next character is prime (or it's the last character)
33 if i >= minLength and char not in prime_digits and (i == n or s[i] in prime_digits):
34 # If all conditions are satisfied, count this as a potential partition endpoint
35 for j in range(1, k + 1):
36 f[i][j] = g[i - minLength][j - 1]
37
38 # Update g[i][j] to include all partitions counted in f[i][j],
39 # as well as those that were counted up to position i-1
40 for j in range(k + 1):
41 g[i][j] = (g[i - 1][j] + f[i][j]) % mod
42
43 # Return the number of beautiful partitions of the whole string using exactly k partitions
44 return f[n][k]
45
1class Solution {
2 private static final int MOD = (int) 1e9 + 7;
3
4 // Checks if a character is a prime digit
5 private boolean isPrimeChar(char c) {
6 return c == '2' || c == '3' || c == '5' || c == '7';
7 }
8
9 // Returns the number of beautiful partitions of string s
10 public int beautifulPartitions(String s, int k, int minLength) {
11 int length = s.length();
12 // If the first character is not prime or the last character is prime, return 0
13 if (!isPrimeChar(s.charAt(0)) || isPrimeChar(s.charAt(length - 1))) {
14 return 0;
15 }
16
17 // DP table: f[i][j] to store number of ways to partition substring of length i with j beautiful partitions
18 int[][] f = new int[length + 1][k + 1];
19 // Prefix sum table: g[i][j] to store prefix sums of f up to index i with j beautiful partitions
20 int[][] g = new int[length + 1][k + 1];
21
22 // Base case (empty string with 0 partitions)
23 f[0][0] = 1;
24 g[0][0] = 1;
25
26 // Go through each character in the string
27 for (int i = 1; i <= length; ++i) {
28 // Check the conditions for forming a beautiful partition
29 if (i >= minLength && !isPrimeChar(s.charAt(i - 1)) && (i == length || isPrimeChar(s.charAt(i)))) {
30 for (int j = 1; j <= k; ++j) {
31 f[i][j] = g[i - minLength][j - 1]; // Use the value from prefix sum table if the substring is beautiful
32 }
33 }
34 // Update the prefix sum table g with the current values
35 for (int j = 0; j <= k; ++j) {
36 g[i][j] = (g[i - 1][j] + f[i][j]) % MOD;
37 }
38 }
39
40 // Return the result from the DP table for full string length with exactly k partitions
41 return f[length][k];
42 }
43}
44
1class Solution {
2public:
3 static const int MOD = 1e9 + 7; // Define modulo constant for large numbers
4
5 // Function to count the number of beautiful partitions
6 int beautifulPartitions(string s, int partitionCount, int minLength) {
7 int strLength = s.size(); // Length of the string
8
9 // Lambda function to check if a character represents a prime digit
10 auto isPrime = [](char c) {
11 return c == '2' || c == '3' || c == '5' || c == '7';
12 };
13 // Return 0 if the first character is not prime or the last character is prime
14 if (!isPrime(s[0]) || isPrime(s[strLength - 1])) return 0;
15
16 // Dynamic programming tables to keep track of ways to make partitions
17 vector<vector<int>> waysToReach(n + 1, vector<int>(partitionCount + 1));
18 vector<vector<int>> cumulativeWays(n + 1, vector<int>(partitionCount + 1));
19
20 // Base cases: There is only one way to have no partitions for a string of any length
21 waysToReach[0][0] = cumulativeWays[0][0] = 1;
22
23 // Fill the dynamic programming tables
24 for (int i = 1; i <= strLength; ++i) {
25 if (i >= minLength && !isPrime(s[i - 1]) && (i == strLength || isPrime(s[i]))) {
26 for (int j = 1; j <= partitionCount; ++j) {
27 // If a partition ends here, count the ways based on the previous state
28 waysToReach[i][j] = cumulativeWays[i - minLength][j - 1];
29 }
30 }
31 for (int j = 0; j <= partitionCount; ++j) {
32 // Update cumulative ways by adding ways up to the current position
33 cumulativeWays[i][j] = (cumulativeWays[i - 1][j] + waysToReach[i][j]) % MOD;
34 }
35 }
36 // Return the number of ways to reach the end of the string with exactly k partitions
37 return waysToReach[strLength][partitionCount];
38 }
39};
40
1const MOD = 1e9 + 7; // Define modulo constant for large number computations
2
3// Function to check if a character represents a prime digit
4const isPrime = (c: string): boolean => {
5 return c === '2' || c === '3' || c === '5' || c === '7';
6};
7
8// Function to count the number of beautiful partitions
9const beautifulPartitions = (s: string, partitionCount: number, minLength: number): number => {
10 const strLength = s.length; // Length of the string
11
12 // Return 0 if the first character is not prime or the last character is prime
13 if (!isPrime(s[0]) || isPrime(s[strLength - 1])) return 0;
14
15 // Dynamic programming tables to keep track of ways to make partitions
16 const waysToReach: number[][] = Array.from({ length: strLength + 1 }, () => Array(partitionCount + 1).fill(0));
17 const cumulativeWays: number[][] = Array.from({ length: strLength + 1 }, () => Array(partitionCount + 1).fill(0));
18
19 // Base case: There is only one way to have no partitions for a string of any length
20 waysToReach[0][0] = cumulativeWays[0][0] = 1;
21
22 // Fill the dynamic programming tables
23 for (let i = 1; i <= strLength; ++i) {
24 if (i >= minLength && !isPrime(s[i - 1]) && (i === strLength || isPrime(s[i]))) {
25 for (let j = 1; j <= partitionCount; ++j) {
26 // If a partition ends here, count the ways based on the previous state
27 waysToReach[i][j] = cumulativeWays[i - minLength][j - 1];
28 }
29 }
30 for (let j = 0; j <= partitionCount; ++j) {
31 // Update cumulative ways by adding ways up to the current position
32 cumulativeWays[i][j] = (cumulativeWays[i - 1][j] + waysToReach[i][j]) % MOD;
33 }
34 }
35 // Return the number of ways to reach the end of the string with exactly 'partitionCount' partitions
36 return waysToReach[strLength][partitionCount];
37};
38
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
(withn
being the length ofs
) and the inner loop runs fork + 1
times. - Within the inner loop, each operation is constant time, where we simply check conditions and update the values of
f[i][j]
andg[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, andk + 1
times for the inner loop), which simplifies toO(n * k)
.
Space Complexity
The space complexity of the given code is O(n * k)
. Here's the breakdown:
- Two 2D arrays
f
andg
are allocated with dimensions(n + 1) * (k + 1)
. Each array holdsn + 1
rows andk + 1
columns of integer values, which means they each requireO(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.
Which of the following array represent a max heap?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!