Leetcode Problem 2478. Number of Beautiful Partitions

2478. Number of Beautiful Partitions

Leetcode Solutions

Dynamic Programming with Prefix Sum Optimization

  1. Initialize a 2D array dp of size (n + 1) x (k + 1) with all elements set to 0, where n is the length of the string s. Set dp[n][0] to 1, as there is one way to partition an empty string with 0 partitions left.
  2. Initialize a 2D array primesum of size (k + 1) x (n + 1) with all elements set to 0. This array will store prefix sums of the dp array.
  3. Iterate over the string s in reverse, starting from the last index and moving towards the first.
  4. For each index i, check if the character at s[i] is a prime digit.
  5. If it is a prime digit, update dp[i][l] for all l from 1 to k by adding the value of primesum[l - 1][-minLength] to it.
  6. Update the primesum array by adding the current dp[i][l] value to the last element of primesum[l] if s[i] is a prime digit and i is the first index or the previous character is not a prime digit.
  7. Return dp[0][k] modulo 10^9 + 7 as the final answer.
UML Thumbnail

D Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...