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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition String Into Minimum Beautiful Substrings

Number: 2883

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a binary string s, partition the string into one or more substrings such that each substring is "beautiful". A substring is defined as beautiful if it does not have leading zeros and it represents the binary form of a number that is a power of 5. Return the minimum number of beautiful substrings needed for the partition; if no such partition exists, return -1.

Key Insights

  • A valid beautiful substring must not start with '0'.
  • Convert the substring from binary to an integer and check if it is a power of 5.
  • Given the small constraint (s.length ≤ 15), a dynamic programming (DP) approach that tries all possible splits is efficient.
  • Use DP where dp[i] represents the minimum number of beautiful substrings that can partition the prefix ending at index i-1.

Space and Time Complexity

Time Complexity: O(n^2 * log(max_value)) where n is the length of the string and the inner log(max_value) factor comes from checking if a number is a power of 5. Space Complexity: O(n) for the DP array.

Solution

We use a dynamic programming approach. First, we define a helper function isBeautiful(substring) that checks if a substring (without leading zeros) represents a power of 5 by converting it from binary to an integer and repeatedly dividing by 5. Then, we populate a DP table where dp[i] stores the minimum partitions needed for the prefix s[0:i]. For every possible split ending at position i, we check if the substring is beautiful; if it is, we update dp[i] using dp[j] + 1, where j is the start index of the substring. Finally, if the entire string can be partitioned, the answer will be in dp[n], otherwise return -1.

Code Solutions

# Python solution for Partition String Into Minimum Beautiful Substrings

def is_beautiful(sub_str):
    # Check for leading zero (but allow single character '1')
    if sub_str[0] == '0':
        return False
    # Convert binary string to integer
    num = int(sub_str, 2)
    # Check if the number is a power of 5
    while num % 5 == 0:
        num //= 5
    return num == 1

def minimumBeautifulSubstrings(s):
    n = len(s)
    # dp[i] will store the minimal number of beautiful substrings for s[0:i]
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # base case: empty string requires 0 substrings

    # Try all possible substrings ending at position i-1
    for i in range(1, n + 1):
        for j in range(i):
            substring = s[j:i]
            # Check if the current substring is beautiful
            if is_beautiful(substring):
                dp[i] = min(dp[i], dp[j] + 1)
    
    # If dp[n] is still infinite then partitioning is not possible
    return dp[n] if dp[n] != float('inf') else -1

# Example usage:
s = "1011"
print(minimumBeautifulSubstrings(s))  # Expected output: 2
← Back to All Questions