LeetCode 2767 - Partition String Into Minimum Beautiful Substrings

The problem asks us to partition a given binary string s into the minimum number of substrings such that each substring is beautiful. A substring is beautiful if it represents a power of 5 in decimal and does not have leading zeros.

leetcodemediumhash-tablestringdynamic-programmingbacktracking

LeetCode Problem 2767

Difficulty: 🟡 Medium
Topics: Hash Table, String, Dynamic Programming, Backtracking

Solution

Problem Understanding

The problem asks us to partition a given binary string s into the minimum number of substrings such that each substring is beautiful. A substring is beautiful if it represents a power of 5 in decimal and does not have leading zeros. The string s contains only '0' and '1' characters, and its length is at most 15, which suggests that exhaustive search is feasible but can be optimized.

The input is a string of length up to 15, meaning the maximum number of substrings is 15 if each '1' is treated individually. The output is the minimum number of beautiful substrings, or -1 if it's impossible to form any valid partition. Key observations include that '0' alone is never beautiful, and substrings cannot start with '0' unless the substring itself is "0", which is invalid.

Important edge cases are strings composed entirely of zeros, strings with single characters, or strings where only some partitions are valid powers of 5.

Approaches

Brute Force

The brute-force approach is to try all possible partitions of the string s and check whether each substring in a partition is a beautiful number. For a string of length n, there are 2^(n-1) possible partitions because each position between characters can either be a split or not. For each partition, we would need to verify if each substring represents a power of 5 without leading zeros. While correct, this approach grows exponentially and is inefficient even for n = 15.

Optimal Approach

The optimal approach uses dynamic programming with memoization. Define dp[i] as the minimum number of beautiful substrings for the suffix starting at index i. For each index i, we try extending a substring s[i:j+1] and check if it is a beautiful number. If it is, we recursively compute dp[j+1] and take the minimum. This avoids recalculating solutions for overlapping subproblems. Precomputing powers of 5 up to the maximum binary number of length 15 allows fast lookup for beauty checks.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generate all partitions and validate each substring
Optimal O(n^2) O(n + m) DP with memoization, precompute powers of 5, m = number of powers ≤ 2^15

Algorithm Walkthrough

  1. Precompute Powers of 5: Generate all powers of 5 that can be represented as binary strings up to length 15, storing them in a set for O(1) lookup.
  2. Initialize DP Array: Create an array dp of size n+1 where dp[i] stores the minimum number of beautiful substrings for the suffix starting at index i. Set dp[n] = 0 since an empty suffix requires no partitions.
  3. Iterate Backwards: For each position i from n-1 down to 0, attempt all substrings starting at i.
  4. Check Beauty: For each substring s[i:j+1], skip if it starts with '0' or is not in the precomputed set of powers of 5. If valid, update dp[i] = min(dp[i], 1 + dp[j+1]).
  5. Return Result: After filling the DP array, if dp[0] is infinity (no valid partitions), return -1. Otherwise, return dp[0].

Why it works: Each position i computes the minimum partitions for the suffix starting there, ensuring overlapping subproblems are reused. The precomputed set guarantees O(1) checks for substring beauty. By trying all valid substring splits, we guarantee the global minimum.

Python Solution

class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        n = len(s)
        powers_of_5 = set()
        num = 1
        max_val = (1 << n) - 1  # Maximum value that can be represented with n bits
        while num <= max_val:
            powers_of_5.add(bin(num)[2:])
            num *= 5
        
        dp = [float('inf')] * (n + 1)
        dp[n] = 0
        
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue
            for j in range(i, n):
                sub = s[i:j+1]
                if sub in powers_of_5:
                    dp[i] = min(dp[i], 1 + dp[j+1])
        
        return -1 if dp[0] == float('inf') else dp[0]

The implementation first precomputes powers of 5 as binary strings. The DP array stores the minimum partitions for each suffix. We iterate backward and check all valid substrings. Leading zeros are handled by skipping any substring starting with '0'.

Go Solution

import "math/bits"

func minimumBeautifulSubstrings(s string) int {
    n := len(s)
    powersOf5 := make(map[string]bool)
    num := 1
    maxVal := (1 << n) - 1
    for num <= maxVal {
        powersOf5[intToBinary(num)] = true
        num *= 5
    }
    
    dp := make([]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = 1<<30 // infinity
    }
    dp[n] = 0
    
    for i := n - 1; i >= 0; i-- {
        if s[i] == '0' {
            continue
        }
        for j := i; j < n; j++ {
            sub := s[i : j+1]
            if powersOf5[sub] {
                if dp[j+1]+1 < dp[i] {
                    dp[i] = dp[j+1] + 1
                }
            }
        }
    }
    
    if dp[0] >= 1<<30 {
        return -1
    }
    return dp[0]
}

func intToBinary(num int) string {
    if num == 0 {
        return "0"
    }
    res := ""
    for num > 0 {
        if num&1 == 1 {
            res = "1" + res
        } else {
            res = "0" + res
        }
        num >>= 1
    }
    return res
}

In Go, we use a map to store powers of 5 as binary strings. DP is initialized to a large number representing infinity. Substrings are sliced using s[i:j+1], and updates to dp[i] are done using min comparisons.

Worked Examples

Example 1: s = "1011"

i Substring Is Beautiful dp[i] update
3 "1" Yes dp[3] = 1
0 "101" Yes dp[0] = 1 + dp[3] = 2
0 "1011" No no update

Result: 2.

Example 2: s = "111"

i Substring Is Beautiful dp[i] update
2 "1" Yes dp[2] = 1
1 "1" Yes dp[1] = 1 + dp[2] = 2
0 "1" Yes dp[0] = 1 + dp[1] = 3

Result: 3.

Example 3: s = "0"

No substring is beautiful. Result: -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) For each starting index, we try all possible ending indices, checking a substring in O(1) via the set.
Space O(n + m) DP array of size n+1 and precomputed powers of 5 as binary strings, m = number of powers ≤ 2^15.

The quadratic time is acceptable because n <= 15. Precomputing powers of 5 is very small as there are at most 15 numbers to consider.

Test Cases

# Provided examples
assert Solution().minimumBeautifulSubstrings("1011") == 2  # ["101","1"]
assert Solution().minimumBeautifulSubstrings("111") == 3   # ["1","1","1"]
assert Solution().minimumBeautifulSubstrings("0") == -1     # impossible

# Single character
assert Solution().minimumBeautifulSubstrings("1") == 1      # ["1"]
assert Solution().minimumBeautifulSubstrings("10") == 1     # ["10"] = 2 in decimal is not power of 5 -> -1

# Leading zeros
assert Solution().minimumBeautifulSubstrings("0101") == -1   # invalid due to leading zero

# Max length
assert Solution().minimumBeautifulSubstrings("101010101010101") >= 1 # arbitrary long input

# Conse