Number of Beautiful Partitions - Video Solutions

Problem Overview: You are given a numeric string s. Split it into exactly k substrings where each substring has length ≥ minLength, starts with a prime digit (2,3,5,7), and ends with a non‑prime digit. The goal is to count how many such valid partitionings exist.

Approach 1: Recursive with Memoization (Top‑Down DP) (Time: O(n * k), Space: O(n * k))

This approach models the problem as a decision process over partition boundaries. Starting from index i, you attempt to create the next partition if the character is a valid prime start. For each possible endpoint satisfying minLength and the non‑prime ending rule, recursively compute the number of ways to form the remaining k-1 partitions. Memoization caches results for states defined by (index, remainingPartitions) to avoid recomputing overlapping subproblems. The recursion naturally fits the structure of the problem but still relies on pruning invalid starts and respecting minimum length constraints. This pattern is common in dynamic programming problems over string partitioning.

Approach 2: Dynamic Programming with Prefix Optimization (Time: O(n * k), Space: O(n * k))

The optimized solution converts the recursion into a bottom‑up DP table. Let dp[i][j] represent the number of ways to form j valid partitions using the first i characters. A partition boundary is only valid if the previous character is non‑prime and the next character is prime. Precompute all valid split positions, then iterate over partition counts while maintaining prefix sums to quickly accumulate transitions. This avoids scanning all previous indices for every state. The algorithm processes the string once per partition count, which keeps the complexity at O(n * k). This technique frequently appears in advanced DP problems where transitions depend on ranges rather than single states.

Recommended for interviews: The bottom‑up dynamic programming approach is the expected solution. It demonstrates that you can translate recursive partition logic into an efficient iterative DP and optimize transitions with prefix sums. The memoized recursion is still valuable because it shows how to reason about the state definition and constraints before optimizing.