Partition String Into Minimum Beautiful Substrings

Problem

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

Examples

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

Solution

Method 1 – Dynamic Programming with Precomputed Powers of 5

Intuition

The key idea is to partition the string such that every substring is a binary representation of a power of 5 and does not have leading zeros. Since the string is short (length ≤ 15), we can use dynamic programming to try all possible partitions efficiently. We precompute all possible binary strings representing powers of 5 up to the maximum possible value for the given length.

Approach

1. Precompute all binary strings (without leading zeros) that represent powers of 5 and have length ≤ n (where n is the length of s).
2. Use dynamic programming: let dp[i] be the minimum number of beautiful substrings for the prefix s[0:i].
3. For each position i, try all possible previous positions j < i such that s[j:i] is a beautiful substring (i.e., in our precomputed set).
4. If possible, update dp[i] = min(dp[i], dp[j] + 1).
5. The answer is dp[n] if it is finite, otherwise -1.

Code

C++

class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        unordered_set<string> pow5;
        for (int i = 0; i < 15; ++i) {
            int val = pow(5, i);
            string bin = bitset<15>(val).to_string();
            bin = bin.substr(bin.find('1'));
            pow5.insert(bin);
        }
        int n = s.size();
        vector<int> dp(n + 1, 20);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                string sub = s.substr(j, i - j);
                if (pow5.count(sub)) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n] > n ? -1 : dp[n];
    }
};

Go

func minimumBeautifulSubstrings(s string) int {
    pow5 := map[string]bool{}
    for i := 0; i < 15; i++ {
        val := 1
        for j := 0; j < i; j++ {
            val *= 5
        }
        bin := strconv.FormatInt(int64(val), 2)
        pow5[bin] = true
    }
    n := len(s)
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = 20
    }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if pow5[s[j:i]] {
                if dp[j]+1 < dp[i] {
                    dp[i] = dp[j] + 1
                }
            }
        }
    }
    if dp[n] > n {
        return -1
    }
    return dp[n]
}

Java

class Solution {
    public int minimumBeautifulSubstrings(String s) {
        Set<String> pow5 = new HashSet<>();
        for (int i = 0; i < 15; i++) {
            int val = (int)Math.pow(5, i);
            String bin = Integer.toBinaryString(val);
            pow5.add(bin);
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 20);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (pow5.contains(s.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n] > n ? -1 : dp[n];
    }
}

Kotlin

class Solution {
    fun minimumBeautifulSubstrings(s: String): Int {
        val pow5 = mutableSetOf<String>()
        for (i in 0 until 15) {
            val bin = Integer.toBinaryString(Math.pow(5.0, i.toDouble()).toInt())
            pow5.add(bin)
        }
        val n = s.length
        val dp = IntArray(n + 1) { 20 }
        dp[0] = 0
        for (i in 1..n) {
            for (j in 0 until i) {
                if (pow5.contains(s.substring(j, i))) {
                    dp[i] = minOf(dp[i], dp[j] + 1)
                }
            }
        }
        return if (dp[n] > n) -1 else dp[n]
    }
}

Python

class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        pow5: set[str] = set()
        for i in range(15):
            val = 5 ** i
            bin_str = bin(val)[2:]
            pow5.add(bin_str)
        n = len(s)
        dp: list[int] = [20] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for j in range(i):
                if s[j:i] in pow5:
                    dp[i] = min(dp[i], dp[j] + 1)
        return -1 if dp[n] > n else dp[n]

Rust

impl Solution {
    pub fn minimum_beautiful_substrings(s: String) -> i32 {
        let mut pow5 = std::collections::HashSet::new();
        for i in 0..15 {
            let val = 5_i32.pow(i);
            let bin = format!("{:b}", val);
            pow5.insert(bin);
        }
        let n = s.len();
        let mut dp = vec![20; n + 1];
        dp[0] = 0;
        let s_bytes = s.as_bytes();
        for i in 1..=n {
            for j in 0..i {
                if pow5.contains(std::str::from_utf8(&s_bytes[j..i]).unwrap()) {
                    dp[i] = dp[i].min(dp[j] + 1);
                }
            }
        }
        if dp[n] > n as i32 { -1 } else { dp[n] }
    }
}

TypeScript

class Solution {
    minimumBeautifulSubstrings(s: string): number {
        const pow5 = new Set<string>();
        for (let i = 0; i < 15; i++) {
            const bin = (5 ** i).toString(2);
            pow5.add(bin);
        }
        const n = s.length;
        const dp = Array(n + 1).fill(20);
        dp[0] = 0;
        for (let i = 1; i <= n; i++) {
            for (let j = 0; j < i; j++) {
                if (pow5.has(s.slice(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n] > n ? -1 : dp[n];
    }
}

Complexity

• ⏰ Time complexity: O(n^2 * L), where n is the length of s (≤ 15), and L is the maximum length of a substring (≤ 15). For each position, we check all previous positions and substring lookup is O(L).
• 🧺 Space complexity: O(2^L), for storing all possible binary strings of powers of 5 up to length L, and O(n) for the dp array.