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 **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 <= 15s[i]is either'0'or'1'.
Solution (Java)
import java.util.Arrays;
public class Solution {
public boolean isFive(int num) {
while (num > 1) {
if (num % 5 != 0) {
return false;
}
num /= 5;
}
return num == 1;
}
public boolean isSubstringBeautiful(int i, int j, String s) {
String str = s.substring(i, j + 1);
int k = 0;
while (k < str.length()) {
if (str.charAt(k) == '0') {
k++;
return false;
} else {
break;
}
}
int ans = 0;
for (int m = str.length() - 1; m >= 0; m--) {
if (str.charAt(m) == '1') {
ans += (1 << (str.length() - 1 - m));
}
}
return isFive(ans);
}
public int func(int idx, String s, int[] dp) {
if (idx == s.length())
return 0;
if (dp[idx] != -1)
return dp[idx];
int min_part = (int) 1e9;
for (int j = idx; j < s.length(); j++) {
if (isSubstringBeautiful(idx, j, s)) {
int cost = 1 + func(j + 1, s, dp);
min_part = Math.min(cost, min_part);
}
}
dp[idx] = min_part;
return min_part;
}
public int minimumBeautifulSubstrings(String s) {
int[] dp = new int[s.length() + 1];
Arrays.fill(dp, -1);
int x = func(0, s, dp);
return x == 1e9 ? -1 : x;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).