Watch 5 video solutions for Partition String Into Minimum Beautiful Substrings, a medium level problem involving Hash Table, String, Dynamic Programming. This walkthrough by Prakhar Agrawal has 1,253 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |