We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition String Into Minimum Beautiful Substrings

Difficulty: Medium

Problem Description

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 and is the binary representation of a number that is a power of 5. Return the minimum number of substrings in such a partition. If it is impossible to partition the string s into beautiful substrings, return -1.

Key Insights

  • A beautiful substring cannot start with '0' unless it is the string "0" itself.
  • The binary representation of powers of 5 can be precomputed since they are limited by the constraints (length of s is at most 15).
  • The powers of 5 in binary representation are: 1 (5^0), 5 (5^1), 25 (5^2), 125 (5^3), 625 (5^4), and 3125 (5^5), which correspond to binary strings "1", "101", "11001", "1111101", "1001110001", and "110000110101".
  • A backtracking approach can be used to find all possible partitions of the string into beautiful substrings.

Space and Time Complexity

Time Complexity: O(2^n) - In the worst case, we may generate all possible substrings. Space Complexity: O(n) - For the recursion stack in the backtracking approach.

Solution

To solve this problem, we can use a backtracking approach to explore all possible partitions of the string. We will maintain a set of beautiful substrings by comparing each substring against precomputed binary representations of powers of 5. If a valid beautiful substring is found, we will proceed to the next part of the string. If we reach the end of the string successfully, we count the number of beautiful substrings formed.

Code Solutions

def minBeautifulSubstrings(s: str) -> int:
    # Precomputed binary representations of powers of 5
    beautiful_numbers = {"1", "101", "11001", "1111101", "1001110001", "110000110101"}
    
    def backtrack(start: int) -> int:
        if start == len(s):
            return 0  # No more characters left, valid partition
        count = float('inf')
        for end in range(start + 1, len(s) + 1):
            substring = s[start:end]
            if substring in beautiful_numbers:
                # If valid beautiful substring, recurse for the rest of the string
                result = backtrack(end)
                if result != -1:
                    count = min(count, result + 1)  # Add one for this substring
        return count if count != float('inf') else -1
    
    # Edge case: string cannot start with '0'
    if s[0] == '0':
        return -1
    return backtrack(0)
← Back to All Questions