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'.The key observation for #2767 Partition String Into Minimum Beautiful Substrings is that a substring is considered beautiful if it represents a power of 5 in binary and does not contain leading zeros. Since the input size is relatively small, we can precompute all binary representations of powers of 5 that fit within the maximum string length.
A practical strategy is to use dynamic programming with backtracking or memoization. Starting from index i, try extending the substring to every possible j and check whether s[i..j] exists in the precomputed set of valid power-of-5 binaries. If it does, recursively compute the minimum partitions for the remaining suffix and track the minimum count.
Memoization avoids recomputing overlapping states, reducing the search space significantly. This approach ensures efficient exploration while keeping substring validation constant-time using a hash set.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking | O(2^n) worst case | O(n) |
| Dynamic Programming with Memoization | O(n^2) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
To check if number x is a power of 5 or not, we will divide x by 5 while x > 1 and x mod 5 == 0. After iteration if x == 1, then it was a power of 5.
Since the constraint of s.length is small, we can use recursion to find all the partitions.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Leading zeros would change the numeric interpretation of a binary number and could create multiple representations for the same value. The constraint ensures each substring represents a valid binary form of a power of 5.
Yes, problems like this appear in coding interviews because they test string manipulation, recursion, and dynamic programming. Companies often use similar partitioning problems to evaluate problem-solving and optimization skills.
A hash set is ideal for storing the binary representations of powers of 5. This allows constant-time validation of whether a substring forms a valid beautiful number during the DP or backtracking process.
The optimal approach uses dynamic programming with memoization. Precompute binary representations of powers of 5 and check valid substrings while recursively minimizing partitions from each index.