Partition String Into Minimum Beautiful Substrings solution and explanation
4 more videos on this problem
Leetcode BiWeekly contest 108 - Medium - Partition String Into Minimum Beautiful SubstringsPrakhar Agrawal · 11:40 · 1K views
Partition String Into Minimum Beautiful Substrings | Leetcode 2767 | Recursion + Memo | C++Tech Courses · 17:33 · 886 views
2767. Partition String Into Minimum Beautiful Substrings (Leetcode Medium)Programming Live with Larry · 9:23 · 498 views
6923. Partition String Into Minimum Beautiful Substrings || Leetcode || Biweekly contest 108 ||HindiAshish Kumar · 10:41 · 212 views
[Eng] Leetcode Biweekly Contest 108 | 2767 Partition String Into Minimum Beautiful SubstringsCyCode · 9:58 · 101 views
The 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 <= 15s[i]is either'0'or'1'.
Approach overview
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 1: Dynamic Programming Approach
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.
def is_power_of_five(n):
while n % 5 == 0 and n != 0:
n /= 5
return n == 1
def min_beautiful_substrings(s):
n = len(s)
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
for j in range(i):
if s[j] == '0':
continue
if is_power_of_five(int(s[j:i], 2)):
dp[i] = min(dp[i], dp[j] + 1)
return dp[n] if dp[n] != float('inf') else -1
# Example usage
s = "1011"
print(min_beautiful_substrings(s)) # Output: 2class Solution {
private boolean isPowerOfFive(int n) {
while (n % 5 == 0 && n > 0) {
n /= 5;
}
return n == 1;
}
public int minBeautifulSubstrings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (s.charAt(j) == '0') continue;
int value = Integer.parseInt(s.substring(j, i), 2);
if (isPowerOfFive(value)) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minBeautifulSubstrings("1011")); // Output: 2
}
}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.
Approach 2: Backtracking Approach
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.
def is_power_of_five(n):
while n % 5 == 0 and n != 0:
n //= 5
return n == 1
def backtrack(s, start):
if start == len(s):
return 0
min_parts = float('inf')
for end in range(start + 1, len(s) + 1):
if s[start] == '0':
break
num = int(s[start:end], 2)
if is_power_of_five(num):
result = backtrack(s, end)
if result != -1:
min_parts = min(min_parts, result + 1)
return -1 if min_parts == float('inf') else min_parts
def min_beautiful_substrings(s):
return backtrack(s, 0)
# Example usage
s = "1011"
print(min_beautiful_substrings(s)) # Output: 2function isPowerOfFive(n) {
while (n % 5 === 0 && n !== 0) {
n /= 5;
}
return n === 1;
}
function backtrack(s, start) {
if (start === s.length) {
return 0;
}
let minParts = Infinity;
for (let end = start + 1; end <= s.length; end++) {
if (s[start] === '0') break;
let num = parseInt(s.substring(start, end), 2);
if (isPowerOfFive(num)) {
let result = backtrack(s, end);
if (result !== -1) {
minParts = Math.min(minParts, result + 1);
}
}
}
return minParts === Infinity ? -1 : minParts;
}
function minBeautifulSubstrings(s) {
return backtrack(s, 0);
}
// Example usage
const s = "1011";
console.log(minBeautifulSubstrings(s)); // Output: 2This 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.
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.
Approach 3: Memoization Search
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:
- If
i geq n, it means that all the characters have been processed, and the answer is0; - If
s[i] = 0, it means that the current string contains leading0, which does not conform to the definition of a beautiful string, so the answer is infinite; - Otherwise, we enumerate the end position
jof the substring fromi, and usexto represent the decimal value of the substrings[i..j]. Ifxis in the hash tabless, then we can takes[i..j]as a beautiful substring, and the answer is1 + dfs(j + 1). We need to enumerate all possiblejand 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.
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;
}
};function minimumBeautifulSubstrings(s: string): number {
const ss: Set<number> = new Set();
const n = s.length;
const f: number[] = new Array(n).fill(-1);
for (let i = 0, x = 1; i <= n; ++i) {
ss.add(x);
x *= 5;
}
const dfs = (i: number): number => {
if (i === n) {
return 0;
}
if (s[i] === '0') {
return n + 1;
}
if (f[i] !== -1) {
return f[i];
}
f[i] = n + 1;
for (let j = i, x = 0; j < n; ++j) {
x = (x << 1) | (s[j] === '1' ? 1 : 0);
if (ss.has(x)) {
f[i] = Math.min(f[i], 1 + dfs(j + 1));
}
}
return f[i];
};
const ans = dfs(0);
return ans > n ? -1 : ans;
}func minimumBeautifulSubstrings(s string) int {
ss := map[int]bool{}
n := len(s)
x := 1
f := make([]int, n+1)
for i := 0; i <= n; i++ {
ss[x] = true
x *= 5
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if s[i] == '0' {
return n + 1
}
if f[i] != -1 {
return f[i]
}
f[i] = n + 1
x := 0
for j := i; j < n; j++ {
x = x<<1 | int(s[j]-'0')
if ss[x] {
f[i] = min(f[i], 1+dfs(j+1))
}
}
return f[i]
}
ans := dfs(0)
if ans > n {
return -1
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Partition String Into Minimum Beautiful Substrings easy or hard?
This problem is considered medium difficulty. The main challenge is recognizing that valid substrings correspond to powers of 5 in binary and combining that observation with dynamic programming or backtracking to compute the minimum partition count.
How to solve Partition String Into Minimum Beautiful Substrings in O(n^2)?
Store all binary representations of powers of 5 whose length is at most n. Use dynamic programming where dp[i] represents the minimum partitions for the prefix s[0:i]. For every i, iterate j from 0 to i and check whether substring s[j:i] is a valid power of 5 without leading zeros, updating dp[i] accordingly.
Partition String Into Minimum Beautiful Substrings Python or Java solution?
Both Python and Java implementations typically follow the same dynamic programming logic. Precompute binary powers of 5, store them in a set, then iterate through the string updating dp values based on valid substrings. The algorithm runs in O(n^2) time and O(n) space in both languages.
What is the best approach for Partition String Into Minimum Beautiful Substrings?
Dynamic programming is the most practical approach. Precompute binary representations of powers of 5 and store them in a hash set. Then use a DP array where dp[i] stores the minimum partitions for the prefix ending at i. Checking all split points results in O(n^2) time and O(n) space complexity.
Is Partition String Into Minimum Beautiful Substrings asked at Google/Amazon/Meta?
Problems involving string partitioning and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear verbatim, the underlying pattern—partitioning a string based on numeric or structural constraints—is common in coding interviews.
What data structure is used in Partition String Into Minimum Beautiful Substrings?
The main data structures are a dynamic programming array and a hash set. The DP array stores the minimum number of partitions for prefixes, while the hash set enables constant-time lookup to check whether a substring represents a power of 5.
What is the time complexity of Partition String Into Minimum Beautiful Substrings?
The optimized dynamic programming solution runs in O(n^2) time because each index checks all previous split points. Space complexity is O(n) for the DP array and the set of valid binary power-of-5 strings. A pure backtracking approach can degrade to O(2^n) in the worst case.