Number of Beautiful Partitions

Number of Beautiful Partitions

What is this problem about?

The Number of Beautiful Partitions problem gives you a numeric string and integers k and minLength. Partition the string into exactly k substrings such that each substring starts with a prime digit and ends with a non-prime digit, and has length ≥ minLength. Count valid partitions modulo 10^9+7. This hard coding problem uses DP with prefix sum optimization on valid partition points.

Why is this asked in interviews?

Google asks this hard problem because it combines DP partition counting with prefix sums for O(1) transition cost — a technique that reduces O(n²k) DP to O(nk). The string, dynamic programming, and prefix sum interview pattern is comprehensively tested, and the prime/non-prime digit conditions add a layer of constraint checking.

Algorithmic pattern used

DP with prefix sums. Define dp[i][j] = number of ways to partition the first i characters into j groups. Transition: the j-th group ends at position i and starts at some position s, where s has a prime digit, i has a non-prime digit, and i - s + 1 ≥ minLength. Use prefix sums prefDP[i][j-1] to efficiently sum over all valid starting positions. Prime digits: {2,3,5,7}. Non-prime: {1,4,6,8,9,0}.

Example explanation

s="23542185131", k=3, minLength=2.

• Valid start characters (prime digits): 2,3,5,7.
• Valid end characters (non-prime digits): 1,4,6,8,9,0.
• Find all valid (start, end) pairs with length ≥ 2, count ways to form 3 such partitions covering the entire string.
• DP with prefix sums computes the answer efficiently.

Common mistakes candidates make

• O(n²k) DP without prefix sum optimization (TLE on large inputs).
• Incorrect prime digit check (forgetting that prime digits are {2,3,5,7}).
• Not applying the minLength constraint when scanning valid start positions.
• Off-by-one in prefix sum indexing.

Interview preparation tip

Partition DP problems where transitions sum over a range of previous states always benefit from prefix sum optimization. Build the prefix sum array in parallel with the DP. For "count partitions into k parts with each part satisfying a condition," first identify valid start/end positions (prime/non-prime check), then apply DP with prefix sums. Practice similar problems like "count ways to partition a string with given prefix/suffix constraints" to build fluency with this combined technique.