2767

2767. Partition String Into Minimum Beautiful Substrings (Medium)

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

Related Topics:
Hash Table, String, Dynamic Programming, Backtracking

Similar Questions:

• Partition Array for Maximum Sum (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/partition-string-into-minimum-beautiful-substrings
// Author: github.com/lzl124631x
// Time: O(2^N * N)
// Space: O(1)
class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        int N = s.size(), ans = INT_MAX;
        for (int m = 1; m < (1 << N); ++m) {
            int i = 0, split = 0;
            while (i < N) {
                int start = i, v = m >> (N - 1 - i) & 1, n = s[i] - '0';
                if (s[i] == '0') {
                    split = -1;
                    break;
                }
                ++i;
                while (i < N && (m >> (N - 1 - i) & 1) == v) {
                    n = (n << 1) + s[i] - '0';
                    ++i;
                }
                while (n % 5 == 0) n /= 5;
                if (n != 1) {
                    split = -1;
                    break;
                }
                ++split;
            }
            if (split != -1) ans = min(ans, split);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

Solution 2. DP

Let dp[i+1] be the min split of s[0..i]. Initially dp[i] = Inf, dp[0] = 0.

dp[i+1] = 1 + min( dp[j] | 0 <= j <= i and s[j..i] is a power of 5 and s[j..i] has no leading 0)

The answer is dp[N].

To check if n is pow of 5, we can check if 15625 % n == 0, where 15625 is the biggest pow of 5 with 15 bits.

// OJ: https://leetcode.com/problems/partition-string-into-minimum-beautiful-substrings
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int minimumBeautifulSubstrings(string s) {
        int N = s.size(), ans = INT_MAX;
        vector<int> dp(N + 1, INT_MAX);
        dp[0] = 0;
        auto isPowerOf5 = [](int n) {
            return 15625 % n == 0
        };
        for (int i = 0; i < N; ++i) {
            int p = 1, n = 0;
            for (int j = i; j >= 0; --j, p <<= 1) {
                if (s[j] == '0') continue;
                n += p;
                if (dp[j] == INT_MAX || !isPowerOf5(n)) continue;
                dp[i + 1] = min(dp[i + 1], 1 + dp[j]);
            }
        }
        return dp[N] == INT_MAX ? -1 : dp[N];
    }
};