# Partition String Into Minimum Beautiful Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-string-into-minimum-beautiful-substrings)
Canonical: https://scaleengineer.com/dsa/problems/partition-string-into-minimum-beautiful-substrings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Hash Table, String
---
## Problem
Given a binary string `s`, partition the string into one or more **substrings** such that each substring is **beautiful**.

A string is **beautiful** if:

* It doesn't contain leading zeros.
* It's the **binary** representation of a number that is a power of `5`.

Return _the **minimum** number of substrings in such partition._ If it is impossible to partition the string `s` into beautiful substrings, return `-1`.

A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** s = "1011"
**Output:** 2
**Explanation:** We can paritition the given string into ["101", "1"].
- The string "101" does not contain leading zeros and is the binary representation of integer 51 = 5.
- The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1.
It can be shown that 2 is the minimum number of beautiful substrings that s can be partitioned into.

**Example 2:**

**Input:** s = "111"
**Output:** 3
**Explanation:** We can paritition the given string into ["1", "1", "1"].
- The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1.
It can be shown that 3 is the minimum number of beautiful substrings that s can be partitioned into.

**Example 3:**

**Input:** s = "0"
**Output:** -1
**Explanation:** We can not partition the given string into beautiful substrings.

**Constraints:**

* `1 <= s.length <= 15`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute-force Recursion
This approach explores all possible ways to partition the string `s`. A recursive function is used to try every possible cut point. For each potential substring, we check if it's "beautiful". If it is, we recursively solve for the rest of the string and combine the results to find the minimum number of partitions.
**Time:** O(2^n * n). In the worst case, we explore an exponential number of partitions. For each potential substring, converting it to a number takes O(n) time. · **Space:** O(n), where n is the length of the string. This is for the recursion call stack depth.
**Pros:** Simple to understand and implement as it directly translates the problem statement into a recursive structure.
**Cons:** Highly inefficient due to re-computation of results for the same subproblems.; Likely to cause a 'Time Limit Exceeded' error for larger constraints, though it might pass for `n <= 15`.
### Explanation
We define a recursive function, let's call it `solve(index)`, which calculates the minimum beautiful partitions for the suffix of the string starting at `index`.

The base case for the recursion is when `index` reaches the end of the string (`s.length()`). This means we have successfully partitioned the entire string, so we return 0.

In the recursive step, we iterate from the current `index` to the end of the string. For each `j`, we form a substring `s.substring(index, j + 1)`.

We then check if this substring is "beautiful". A substring is beautiful if it doesn't start with '0' and its decimal value is a power of 5. If the substring is beautiful, we make a recursive call for the remaining part of the string: `solve(j + 1)`. We add 1 to the result of this call (to account for the current beautiful substring) and update our minimum count.

If no beautiful substring can be formed starting from `index`, we return a value indicating impossibility (e.g., infinity). The initial call is `solve(0)`. If the result is infinity, it's impossible to partition, so we return -1.

```java
class Solution {
    public int beautifulPartitions(String s) {
        int result = solve(s, 0);
        // Use a large number for infinity to avoid confusion
        return result >= 1_000_000 ? -1 : result;
    }

    private int solve(String s, int index) {
        if (index == s.length()) {
            return 0;
        }
        if (s.charAt(index) == '0') {
            return 1_000_000;
        }

        int minPartitions = 1_000_000;
        long currentVal = 0;
        for (int j = index; j < s.length(); j++) {
            currentVal = currentVal * 2 + (s.charAt(j) - '0');
            if (isPowerOfFive(currentVal)) {
                int nextPartitions = solve(s, j + 1);
                if (nextPartitions < 1_000_000) {
                    minPartitions = Math.min(minPartitions, 1 + nextPartitions);
                }
            }
        }
        return minPartitions;
    }

    private boolean isPowerOfFive(long n) {
        if (n == 0) return false;
        while (n > 1) {
            if (n % 5 != 0) return false;
            n /= 5;
        }
        return n == 1;
    }
}
```
### Algorithm
- Define a recursive function `solve(index)` that returns the minimum partitions for the suffix `s[index...]`.
- **Base Case:** If `index` equals the string length `n`, a valid partition is found for the whole string, so return 0.
- If the character at `s[index]` is '0', it's impossible to form a beautiful substring, so return a large value (infinity) to signify failure.
- Initialize a variable `minPartitions` to infinity.
- Iterate with a loop variable `j` from `index` to `n-1`.
  - In each iteration, form a number `currentVal` from the substring `s[index...j]`.
  - Check if `currentVal` represents a power of 5.
  - If it is, make a recursive call `solve(j + 1)` for the rest of the string.
  - If the recursive call does not return infinity, it means the rest of the string can be partitioned. Update `minPartitions = min(minPartitions, 1 + result_from_recursive_call)`.
- Return `minPartitions`.
- The initial call will be `solve(0)`. If it returns infinity, no solution exists; otherwise, it's the minimum number of partitions.

## Dynamic Programming (Memoization / Iterative)
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.
**Time:** O(n^2). There are n states (subproblems) to solve. For each state `i`, we iterate from `i` to `n-1`, which is an O(n) loop. The operations inside the loop are constant time. · **Space:** O(n), where n is the length of the string. We use an array of size n for the DP table. The recursive version also uses O(n) space for the call stack.
**Pros:** Highly efficient and optimal for this problem.; Guarantees that each subproblem is solved only once.; The iterative version avoids recursion overhead and potential stack overflow issues on larger inputs.
**Cons:** Requires extra space for the DP table/memoization cache.; The logic can be slightly more complex to formulate compared to a simple brute-force approach.
### Explanation
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.

```java
// 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.

```java
// 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) { /* ... */ }
}
```
### Algorithm
- 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]`.

# Solutions
### Java

```java
class Solution {
private
  Integer[] f;
private
  String s;
private
  Set<Long> ss = new HashSet<>();
private
  int n;
public
  int minimumBeautifulSubstrings(String s) {
    n = s.length();
    this.s = s;
    f = new Integer[n];
    long x = 1;
    for (int i = 0; i <= n; ++i) {
      ss.add(x);
      x *= 5;
    }
    int ans = dfs(0);
    return ans > n ? -1 : ans;
  }
private
  int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (s.charAt(i) == '0') {
      return n + 1;
    }
    if (f[i] != null) {
      return f[i];
    }
    long x = 0;
    int ans = n + 1;
    for (int j = i; j < n; ++j) {
      x = x << 1 | (s.charAt(j) - '0');
      if (ss.contains(x)) {
        ans = Math.min(ans, 1 + dfs(j + 1));
      }
    }
    return f[i] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumBeautifulSubstrings(string s) {
    unordered_set<long long> ss;
    int n = s.size();
    long long x = 1;
    for (int i = 0; i <= n; ++i) {
      ss.insert(x);
      x *= 5;
    }
    int f[n];
    memset(f, -1, sizeof(f));
    function<int(int)> dfs = [&](int i) {
      if (i >= n) {
        return 0;
      }
      if (s[i] == '0') {
        return n + 1;
      }
      if (f[i] != -1) {
        return f[i];
      }
      long long x = 0;
      int ans = n + 1;
      for (int j = i; j < n; ++j) {
        x = x << 1 | (s[j] - '0');
        if (ss.count(x)) {
          ans = min(ans, 1 + dfs(j + 1));
        }
      }
      return f[i] = ans;
    };
    int ans = dfs(0);
    return ans > n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int: @ cache def dfs(i: int) -> int: if i >= n: return 0 if s[i] == "0": return inf x = 0 ans = inf for j in range(i, n): x = x << 1 | int(s[j]) if x in ss: ans = min(ans, 1 + dfs(j + 1)) return ans n = len(s) x = 1 ss = {x} for i in range(n): x *= 5 ss . add(x) ans = dfs(0) return - 1 if ans == inf else ans

```