Skip to main content
Talentd

Partition String Into Minimum Beautiful Substrings - Solution & Explanation

MediumHash TableStringDynamic ProgrammingBacktracking16 min read
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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 is 0;
  • If 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;
  • Otherwise, we enumerate the end position 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(n²)O(n)General solution for interviews and large inputs where predictable performance is required
BacktrackingO(2ⁿ) worst caseO(n)Useful for understanding the search space or when constraints are very small

Video Solution

Leetcode BiWeekly contest 108 - Medium - Partition String Into Minimum Beautiful Substrings • Prakhar Agrawal • 1,273 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Partition String Into Minimum Beautiful Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Substring Partition of Equal Character Frequency

Next

Partition Array for Maximum Sum