Partition String Into Minimum Beautiful Substrings

This approach uses dynamic programming to solve the problem efficiently by breaking it down into overlapping subproblems and solving each subproblem only once. We can implement this using either a top-down (memoization) or a bottom-up (iterative) method. Both have the same time complexity and are optimal for this problem.

• The core idea is to define a state dp[i] representing the minimum number of beautiful partitions for the suffix of the string, s[i..n-1].
• The goal is to find dp[0].
• Base Case: dp[n] = 0, as an empty suffix requires 0 partitions.
• Recurrence Relation: dp[i] = min(1 + dp[j+1]) over all j from i to n-1 such that the substring s[i..j] is beautiful. If no such j exists, dp[i] is infinity.
• This can be implemented in two ways:
  • Top-Down (Memoization): Use a recursive function with a memoization table memo to store results of dp[i]. Before computing, check memo[i]. After computing, store the result in memo[i].
  • Bottom-Up (Iterative): Use an array dp of size n+1. Iterate i from n-1 down to 0. For each i, calculate dp[i] using the already computed values dp[j+1].

The brute-force approach is inefficient because it repeatedly solves the same subproblems. We can optimize this by storing the results of subproblems. Let dp[i] be the minimum number of beautiful partitions for the suffix s[i..n-1]. Our goal is to find dp[0].

Top-Down DP (Memoization) This is a direct optimization of the recursive solution. We use a memoization array (e.g., memo) to store the results of solve(i). Before computing solve(i), we check if the result is already in memo. If so, we return it. Otherwise, we compute it, store it in memo, and then return it. This ensures each state is computed only once.

// Top-Down DP with Memoization
class Solution {
    int[] memo;
    public int beautifulPartitions(String s) {
        int n = s.length();
        memo = new int[n + 1];
        java.util.Arrays.fill(memo, -1);
        int result = solve(s, 0);
        return result >= 1_000_000 ? -1 : result;
    }

    private int solve(String s, int i) {
        if (i == s.length()) return 0;
        if (memo[i] != -1) return memo[i];
        if (s.charAt(i) == '0') return memo[i] = 1_000_000;

        int res = 1_000_000;
        long val = 0;
        for (int j = i; j < s.length(); j++) {
            val = val * 2 + (s.charAt(j) - '0');
            if (isPowerOfFive(val)) {
                res = Math.min(res, 1 + solve(s, j + 1));
            }
        }
        return memo[i] = res;
    }

    private boolean isPowerOfFive(long n) { /* ... */ }
}

Bottom-Up DP (Iterative) This approach builds the solution iteratively, eliminating recursion. We create a dp array of size n+1, initialize dp[n] = 0 and the rest to infinity. We loop from i = n-1 down to 0. For each i, we calculate dp[i] using the values of dp[j+1] that have already been computed.

// Bottom-Up Iterative DP
class Solution {
    public int beautifulPartitions(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, 1_000_000);
        dp[n] = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') continue;
            long val = 0;
            for (int j = i; j < n; j++) {
                val = val * 2 + (s.charAt(j) - '0');
                if (isPowerOfFive(val)) {
                    if (dp[j + 1] < 1_000_000) {
                        dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
                    }
                }
            }
        }
        return dp[0] >= 1_000_000 ? -1 : dp[0];
    }

    private boolean isPowerOfFive(long n) { /* ... */ }
}