Given a binary string s, partition the string into one or more substrings such that each substring is beautiful.
A string is beautiful if:
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 <= 15s[i] is either '0' or '1'.Problem Overview: You are given a binary string s. Split it into the minimum number of substrings such that every substring represents a power of 5 when interpreted as a binary number. Substrings cannot contain leading zeros. If no valid partition exists, return -1.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
The key observation: only a small set of binary numbers represent powers of 5 within the string length limit. Precompute all powers of 5 whose binary representation length is ≤ n and store them in a hash set for O(1) lookup. Then use a dynamic programming array where dp[i] represents the minimum number of valid substrings needed to partition the prefix ending at index i. For each index, iterate backward and check whether s[j:i] is in the power‑of‑5 set and does not start with '0'. If valid, update dp[i] = min(dp[i], dp[j] + 1). This reduces the problem to substring validation plus optimal substructure. Time complexity is O(n²) because each position checks all earlier split points, while space is O(n) for the DP array and set storage.
Approach 2: Backtracking (O(2ⁿ) worst case, O(n) space)
This approach explores every possible partition using backtracking. Start from index 0 and try extending the current substring one character at a time. If the substring starts with '0', stop exploring that branch immediately. Convert the substring to an integer and check if it represents a power of 5. When it does, recursively process the remaining suffix and track the minimum number of partitions found. Pruning occurs naturally because invalid prefixes and leading zeros terminate branches early. Although the theoretical complexity is O(2ⁿ), the input size is small and the pruning keeps the search manageable. The recursion stack requires O(n) space.
Recommended for interviews: The dynamic programming solution is usually expected. It shows you can convert a recursive partitioning problem into a structured DP formulation with efficient substring validation using a hash table. Backtracking demonstrates the brute‑force reasoning process, but DP proves you can optimize overlapping subproblems and achieve predictable O(n²) performance.
The idea is to use dynamic programming to find the minimum number of partitions. We maintain a dp array where dp[i] is the minimum number of beautiful substrings for s[0:i]. We iterate over all possible substrings ending at each position and check if they can form a valid beautiful substring. We update dp[i] using previously computed dp values and the current valid substring count.
This Python code defines a helper function, is_power_of_five, which checks if a number n is a power of 5. The main function, min_beautiful_substrings, initializes a dp array for tracking minimum partitions. It loops through possible substring positions to update dp based on valid beautiful substrings, defined as substrings converting to powers of 5. If a valid partition scheme is found, it returns the minimum number of partitions else returns -1.
Time Complexity: O(n^2 * log m), where n is the length of the binary string and m is the maximum numeric value of a substring considered. Space Complexity: O(n) due to the dp array.
This approach employs backtracking to explore all potential partitions of the string. Starting from the beginning of the string, it extends potential substrings until a valid beautiful substring is formed, then recursively tries to partition the remaining string. The process tracks the minimum number of partitions found, ensuring only the optimal solution is retained.
This backtracking solution, written in Python, recursively explores potential partitions. Starting from each index, it increases a substring until it forms a valid beautiful substring (i.e., a power of 5) then continues searching in the remaining string. If a valid partitioning is found, the function returns the number of partitions, otherwise it returns -1.
Python
JavaScript
Time Complexity: O(2^n), due to the exponential nature of backtracking that explores all possible partitions. Space Complexity: O(n) for the recursion stack.
Since the problem requires us to judge whether a string is the binary representation of a power of 5, we might as well first preprocess all the powers of 5 and record them in a hash table ss.
Next, we design a function dfs(i), which indicates the minimum number of cuts from the i-th character of the string s to the end of the string. Then the answer is dfs(0).
The calculation method of function dfs(i) is as follows:
i geq n, it means that all the characters have been processed, and the answer is 0;s[i] = 0, it means that the current string contains leading 0, which does not conform to the definition of a beautiful string, so the answer is infinite;j of the substring from i, and use x to represent the decimal value of the substring s[i..j]. If x is in the hash table ss, then we can take s[i..j] as a beautiful substring, and the answer is 1 + dfs(j + 1). We need to enumerate all possible j and take the minimum value of all answers.In order to avoid repeated calculation, we can use the method of memory search.
In the main function, we first preprocess all the powers of 5, and then call dfs(0). If the return value is infinite, it means that the string s cannot be divided into beautiful substrings, and the answer returns -1, otherwise, return the value of dfs(0).
Time complexity O(n^2), space complexity O(n). Where n is the length of string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2 * log m), where n is the length of the binary string and m is the maximum numeric value of a substring considered. Space Complexity: O(n) due to the dp array. |
| Backtracking Approach | Time Complexity: O(2^n), due to the exponential nature of backtracking that explores all possible partitions. Space Complexity: O(n) for the recursion stack. |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | General solution for interviews and large inputs where predictable performance is required |
| Backtracking | O(2ⁿ) worst case | O(n) | Useful for understanding the search space or when constraints are very small |
Leetcode BiWeekly contest 108 - Medium - Partition String Into Minimum Beautiful Substrings • Prakhar Agrawal • 1,253 views views
Watch 4 more video solutions →Practice Partition String Into Minimum Beautiful Substrings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor