Problem statement

A binary string is beautiful if it has no leading zeros and, read as a binary number, equals a power of 5 (1, 5, 25, 125, …).

Given a binary string s, split it into one or more contiguous substrings so that every piece is beautiful. Return the minimum number of pieces, or -1 if no such split exists.

Example 1

Input: s = "1011"
Output: 2
Explanation: "101" is 5 and "1" is 1.

Example 2

Input: s = "111"
Output: 3
Explanation: Three pieces of "1".

Example 3

Input: s = "0"
Output: -1
Explanation: A piece cannot start with a zero.

Constraints

• 1 <= s.length <= 15
• s[i] is '0' or '1'

Hints for Partition String Into Minimum Beautiful Substrings

1. Hint 1

   Every piece must start with a 1 (no leading zeros), so a string that starts with 0 can never be split, and a cut can only fall just before a 1.

2. Hint 2

   Let dp[i] be the fewest pieces for the prefix of length i. Try every last piece s[j..i): it must start with 1 and its value must be a power of 5.

3. Hint 3

   Values are below 2^15, so test a power of 5 by dividing by 5 while possible and checking you reach 1 — or precompute the few powers of 5 that fit.

How to solve Partition String Into Minimum Beautiful Substrings

A classic partition DP: the best split of a prefix is one more than the best split of a shorter prefix, over all last pieces that are beautiful.

Approach

1. dp[0] = 0, dp[i] = ∞ for i > 0.
2. For each end i from 1 to n, and each start j < i with s[j] == '1', compute the value of s[j..i); if it is a power of 5 and dp[j] is finite, set dp[i] = min(dp[i], dp[j] + 1).
3. Return dp[n], or -1 if it is still ∞.

Why it works

Every valid split has a last piece s[j..n), and the pieces before it form a valid split of the prefix of length j. Minimising over j with the best split of each prefix is therefore exact.

Complexity

• Time — O(n^2 · log v) — at most 15 × 15 checks
• Space — O(n)

Pitfalls

• "0" is not a power of 5, and a piece like "0101" has a leading zero — both are invalid.
• Return -1 when the string cannot be split at all (for example, when it starts with 0).

Reference solution

Python

def minimumBeautifulSubstrings(s: str) -> int:
    def is_pow5(v):
        if v < 1:
            return False
        while v % 5 == 0:
            v //= 5
        return v == 1

    n = len(s)
    INF = float('inf')
    dp = [0] + [INF] * n
    for i in range(1, n + 1):
        for j in range(i):
            if s[j] == '1' and dp[j] + 1 < dp[i] and is_pow5(int(s[j:i], 2)):
                dp[i] = dp[j] + 1
    return dp[n] if dp[n] != INF else -1

Java

public static int minimumBeautifulSubstrings(String s) {
    int n = s.length(), INF = 1000;
    int[] dp = new int[n + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int j = 0; j < n; j++) {
        if (s.charAt(j) != '1' || dp[j] == INF) continue;
        int v = 0;
        for (int i = j; i < n; i++) {
            v = v * 2 + (s.charAt(i) - '0');
            int t = v;
            while (t % 5 == 0) t /= 5;
            if (t == 1) dp[i + 1] = Math.min(dp[i + 1], dp[j] + 1);
        }
    }
    return dp[n] == INF ? -1 : dp[n];
}

C++

int minimumBeautifulSubstrings(string s) {
    int n = s.size(), INF = 1000;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int j = 0; j < n; j++) {
        if (s[j] != '1' || dp[j] == INF) continue;
        int v = 0;
        for (int i = j; i < n; i++) {
            v = v * 2 + (s[i] - '0');
            int t = v;
            while (t % 5 == 0) t /= 5;
            if (t == 1) dp[i + 1] = min(dp[i + 1], dp[j] + 1);
        }
    }
    return dp[n] == INF ? -1 : dp[n];
}

JavaScript

var minimumBeautifulSubstrings = function(s) {
    var n = s.length, INF = 1000, dp = new Array(n + 1).fill(INF);
    dp[0] = 0;
    for (var j = 0; j < n; j++) {
        if (s[j] !== '1' || dp[j] === INF) continue;
        var v = 0;
        for (var i = j; i < n; i++) {
            v = v * 2 + (s[i] === '1' ? 1 : 0);
            var t = v;
            while (t % 5 === 0) t /= 5;
            if (t === 1 && dp[j] + 1 < dp[i + 1]) dp[i + 1] = dp[j] + 1;
        }
    }
    return dp[n] === INF ? -1 : dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium