LeetCode 2478: Number of Beautiful Partitions
Problem Description
Explanation:
To solve this problem, we can iterate through all possible partitions of the string s and check if each partition satisfies the conditions of being beautiful. We can use dynamic programming to keep track of the number of beautiful partitions ending at each index of the string.
- Initialize a 2D DP array where
dp[i][j]represents the number of beautiful partitions ending at indexiwithjsubstrings. - Iterate through each index
iof the stringsand each possible number of substringsj. - For each index
i, calculate the number of beautiful partitions ending at indexiwithjsubstrings based on the previous results. - Update the DP array accordingly.
- Finally, return the sum of all beautiful partitions with
ksubstrings and a total length of at leastminLength. :
Solutions
class Solution {
public int countBeautifulString(String s, int k, int minLength) {
int mod = 1000000007;
int n = s.length();
int[][] dp = new int[n + 1][k + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int primeCount = 0;
for (int l = i; l > 0 && i - l + 1 >= minLength; l--) {
if (s.charAt(l - 1) == '2' || s.charAt(l - 1) == '3' || s.charAt(l - 1) == '5' || s.charAt(l - 1) == '7') {
primeCount++;
}
if (primeCount > 0) {
dp[i][j] = (dp[i][j] + dp[l - 1][j - 1]) % mod;
}
}
}
}
int result = 0;
for (int i = 0; i <= n; i++) {
result = (result + dp[i][k]) % mod;
}
return result;
}
}Loading editor...