Partition String Into Minimum Beautiful Substrings

Med

#2484Time: 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.

Patterns

Dynamic Programming Backtracking

Data structures

Hash Table String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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].

Walkthrough

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.

1// Top-Down DP with Memoization2class Solution {3    int[] memo;4    public int beautifulPartitions(String s) {5        int n = s.length();6        memo = new int[n + 1];7        java.util.Arrays.fill(memo, -1);8        int result = solve(s, 0);9        return result >= 1_000_000 ? -1 : result;10    }11 12    private int solve(String s, int i) {13        if (i == s.length()) return 0;14        if (memo[i] != -1) return memo[i];15        if (s.charAt(i) == '0') return memo[i] = 1_000_000;16 17        int res = 1_000_000;18        long val = 0;19        for (int j = i; j < s.length(); j++) {20            val = val * 2 + (s.charAt(j) - '0');21            if (isPowerOfFive(val)) {22                res = Math.min(res, 1 + solve(s, j + 1));23            }24        }25        return memo[i] = res;26    }27 28    private boolean isPowerOfFive(long n) { /* ... */ }29}

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.

1// Bottom-Up Iterative DP2class Solution {3    public int beautifulPartitions(String s) {4        int n = s.length();5        int[] dp = new int[n + 1];6        java.util.Arrays.fill(dp, 1_000_000);7        dp[n] = 0;8 9        for (int i = n - 1; i >= 0; i--) {10            if (s.charAt(i) == '0') continue;11            long val = 0;12            for (int j = i; j < n; j++) {13                val = val * 2 + (s.charAt(j) - '0');14                if (isPowerOfFive(val)) {15                    if (dp[j + 1] < 1_000_000) {16                        dp[i] = Math.min(dp[i], 1 + dp[j + 1]);17                    }18                }19            }20        }21        return dp[0] >= 1_000_000 ? -1 : dp[0];22    }23 24    private boolean isPowerOfFive(long n) { /* ... */ }25}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int beautifulPartitions(String s) {3        int result = solve(s, 0);4        // Use a large number for infinity to avoid confusion5        return result >= 1_000_000 ? -1 : result;6    }7 8    private int solve(String s, int index) {9        if (index == s.length()) {10            return 0;11        }12        if (s.charAt(index) == '0') {13            return 1_000_000;14        }15 16        int minPartitions = 1_000_000;17        long currentVal = 0;18        for (int j = index; j < s.length(); j++) {19            currentVal = currentVal * 2 + (s.charAt(j) - '0');20            if (isPowerOfFive(currentVal)) {21                int nextPartitions = solve(s, j + 1);22                if (nextPartitions < 1_000_000) {23                    minPartitions = Math.min(minPartitions, 1 + nextPartitions);24                }25            }26        }27        return minPartitions;28    }29 30    private boolean isPowerOfFive(long n) {31        if (n == 0) return false;32        while (n > 1) {33            if (n % 5 != 0) return false;34            n /= 5;35        }36        return n == 1;37    }38}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  Integer[] f;4private5  String s;6private7  Set<Long> ss = new HashSet<>();8private9  int n;10public11  int minimumBeautifulSubstrings(String s) {12    n = s.length();13    this.s = s;14    f = new Integer[n];15    long x = 1;16    for (int i = 0; i <= n; ++i) {17      ss.add(x);18      x *= 5;19    }20    int ans = dfs(0);21    return ans > n ? -1 : ans;22  }23private24  int dfs(int i) {25    if (i >= n) {26      return 0;27    }28    if (s.charAt(i) == '0') {29      return n + 1;30    }31    if (f[i] != null) {32      return f[i];33    }34    long x = 0;35    int ans = n + 1;36    for (int j = i; j < n; ++j) {37      x = x << 1 | (s.charAt(j) - '0');38      if (ss.contains(x)) {39        ans = Math.min(ans, 1 + dfs(j + 1));40      }41    }42    return f[i] = ans;43  }44}

1class Solution {2public:3  int minimumBeautifulSubstrings(string s) {4    unordered_set<long long> ss;5    int n = s.size();6    long long x = 1;7    for (int i = 0; i <= n; ++i) {8      ss.insert(x);9      x *= 5;10    }11    int f[n];12    memset(f, -1, sizeof(f));13    function<int(int)> dfs = [&](int i) {14      if (i >= n) {15        return 0;16      }17      if (s[i] == '0') {18        return n + 1;19      }20      if (f[i] != -1) {21        return f[i];22      }23      long long x = 0;24      int ans = n + 1;25      for (int j = i; j < n; ++j) {26        x = x << 1 | (s[j] - '0');27        if (ss.count(x)) {28          ans = min(ans, 1 + dfs(j + 1));29        }30      }31      return f[i] = ans;32    };33    int ans = dfs(0);34    return ans > n ? -1 : ans;35  }36};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem