Partition String Into Minimum Beautiful Substrings

Medium

Asked by:

10 views

Topics:

StringsDynamic Programming

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 5¹ = 5.
- The string "1" does not contain leading zeros and is the binary representation of integer 5⁰ = 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 5⁰ = 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'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string? Is there a practical limit on the string's size?
Can the input string be empty or null?
What defines a "beautiful" substring? Is it explicitly limited to powers of 5, or is there a more general criteria?
If the string cannot be partitioned into beautiful substrings, what should the function return? Should I return -1, throw an exception, or is there another specified return value?
If multiple valid partitions exist with the same minimum number of substrings, is any one of them acceptable, or is there a tie-breaking preference, such as choosing the partition with the smallest first substring?

Brute Force Solution

Approach

The brute force approach tries every single possible way to break the string into smaller parts. We check if each part is considered 'beautiful' according to the problem's rules. Then, we find the way to break the string into the fewest number of beautiful parts.

Here's how the algorithm would work step-by-step:

Start by considering the first character of the string as a possible first substring.
Check if this single character is 'beautiful' according to the problem's rules.
Then, consider the first two characters as a possible first substring, and check if that's 'beautiful'.
Keep going, trying the first three characters, four characters, and so on, until you reach the end of the string, and check for 'beautiful' substrings each time.
For each 'beautiful' substring you find at the beginning, repeat the same process for the remaining part of the string after that substring.
Keep doing this until the whole string has been split into 'beautiful' substrings.
Every time you successfully split the entire string, count how many 'beautiful' substrings you used.
After trying all possible ways to split the string, choose the split that uses the smallest number of 'beautiful' substrings.

Code Implementation

def partition_string_into_minimum_beautiful_substrings(input_string):
    minimum_substring_count = float('inf')

    def is_power_of_five(number):
        if number <= 0:
            return False
        while number % 5 == 0:
            number //= 5
        return number == 1

    def solve(start_index, current_substring_count):
        nonlocal minimum_substring_count

        if start_index == len(input_string):
            # If we've reached the end, update the minimum count
            minimum_substring_count = min(minimum_substring_count, current_substring_count)
            return

        if current_substring_count >= minimum_substring_count:
            return

        for end_index in range(start_index + 1, len(input_string) + 1):
            substring = input_string[start_index:end_index]

            if substring[0] == '0':
                continue

            decimal_value = int(substring, 2)

            #Check if substring is beautiful
            if is_power_of_five(decimal_value):

                solve(end_index, current_substring_count + 1)

    solve(0, 0)

    if minimum_substring_count == float('inf'):
        return -1
    return minimum_substring_count

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible partitions of the string. For a string of length n, there are 2^(n-1) possible ways to place dividers between the characters. In the worst case, we might have to check all these partitions to find the minimum number of beautiful substrings. Each partition requires checking if the resulting substrings are beautiful, which can take O(n) time in the worst case for the entire partition. Thus, the overall time complexity becomes O(n * 2^(n-1)), which simplifies to O(2^n).

Space Complexity

O(N) – The described brute force approach utilizes recursion to explore all possible substring partitions. In the worst-case scenario, each recursive call explores a slightly smaller suffix of the input string. This can lead to a maximum recursion depth of N, where N is the length of the input string, with each recursive call consuming stack space. Therefore, the auxiliary space used by the recursion stack is proportional to the length of the input string, N. This leads to a space complexity of O(N).

Optimal Solution

Approach

The goal is to break down the given string into the fewest possible pieces, where each piece is considered beautiful. A beautiful string represents a power of 5. We solve this by trying to use the longest possible beautiful string from the beginning, and then repeating on what's left.

Here's how the algorithm would work step-by-step:

First, create a list of numbers that are powers of 5. These are the beautiful numbers we can use.
Start at the beginning of the input string.
Try to find the largest power of 5 (from our list) that perfectly matches the beginning of the string. If multiple match, always pick the longest.
If you find a power of 5 that matches, cut off that piece from the beginning of the string. This piece is now one of your beautiful substrings.
Repeat the process, starting from the beginning of the remaining string.
Keep going until the entire original string has been split into beautiful substrings.
If at any point, you can't find a power of 5 that matches the beginning of the remaining string, it means there is no solution. You'll have to report this by returning a special value such as negative one or indicate there is no valid split.
Finally, return the number of beautiful substrings you created.

Code Implementation

def partition_string(binary_string):
    powers_of_five = []
    power = 1
    while power <= int(binary_string, 2) if binary_string else 0:
        powers_of_five.append(bin(power)[2:])
        power *= 5

    substring_count = 0
    remaining_string = binary_string

    while remaining_string:
        best_match = None
        # Find the largest power of 5 that matches the start
        for beautiful_number in reversed(powers_of_five):
            if remaining_string.startswith(beautiful_number) and beautiful_number[0] == '1':
                best_match = beautiful_number
                break

        # No match found, invalid partition
        if not best_match:
            return -1

        substring_count += 1
        remaining_string = remaining_string[len(best_match):]

    return substring_count

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the length of the input string and m be the number of powers of 5 we precompute. The algorithm iterates, in the worst case, n times, where each iteration attempts to match the longest possible power of 5 to the beginning of the remaining string. Inside each iteration, it iterates through the precomputed list of m powers of 5 to find the longest match. String comparison to check for the match can be done at O(n) but is limited by the number of powers of 5, so this search takes O(m). Thus, the overall time complexity is O(n*m) because the loop to generate powers of 5 is constant relative to n.

Space Complexity

O(1) – The algorithm creates a list of powers of 5, which is of constant size because the maximum power of 5 representable as a string without exceeding practical length limits is fixed. It also uses a counter for the number of beautiful substrings. Therefore, the auxiliary space used is constant regardless of the input string's length, N.

Edge Cases

Case	How to Handle
Empty string input	Return an empty list or indicate no valid partition if the input string is empty.
String contains characters other than '1' and '0'	Throw an IllegalArgumentException or return an error code to indicate invalid input characters.
String consisting only of '0's	Return an empty list or indicate no valid partition, as '0' is not a valid power of 5.
Very long string that might cause stack overflow with recursion	Use dynamic programming (memoization) or iterative approach to avoid excessive recursion depth.
A substring represents a power of 5 that exceeds integer limits (Integer overflow)	Use long data type to represent the power of 5 and check for overflow during the conversion or limit the input string size.
No valid partition exists	Return an empty list or a special value (e.g., null) to indicate that no beautiful partition is possible.
Maximum sized input string consisting of all '1's	The algorithm should handle a maximum sized input string efficiently without exceeding time limits due to excessive computations.
A very long power of 5 substring	The solution must correctly handle cases when a substring representing a valid power of 5 has a large number of digits and verify it efficiently.

Empty string input

How to Handle:

Return an empty list or indicate no valid partition if the input string is empty.

String contains characters other than '1' and '0'

How to Handle:

Throw an IllegalArgumentException or return an error code to indicate invalid input characters.

String consisting only of '0's

How to Handle:

Return an empty list or indicate no valid partition, as '0' is not a valid power of 5.

Very long string that might cause stack overflow with recursion

How to Handle:

Use dynamic programming (memoization) or iterative approach to avoid excessive recursion depth.

A substring represents a power of 5 that exceeds integer limits (Integer overflow)

How to Handle:

Use long data type to represent the power of 5 and check for overflow during the conversion or limit the input string size.

No valid partition exists

How to Handle:

Return an empty list or a special value (e.g., null) to indicate that no beautiful partition is possible.

Maximum sized input string consisting of all '1's

How to Handle:

The algorithm should handle a maximum sized input string efficiently without exceeding time limits due to excessive computations.

A very long power of 5 substring

How to Handle:

The solution must correctly handle cases when a substring representing a valid power of 5 has a large number of digits and verify it efficiently.