2767. Partition String Into Minimum Beautiful Substrings LeetCode Solution
In this guide, you will get 2767. Partition String Into Minimum Beautiful Substrings LeetCode Solution with the best time and space complexity. The solution to Partition String Into Minimum Beautiful Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Partition String Into Minimum Beautiful Substrings
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.
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'.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
2767. Partition String Into Minimum Beautiful Substrings LeetCode Solution in C++
class Solution {
public:
int minimumBeautifulSubstrings(string s) {
const int n = s.length();
// dp[i] := the minimum number of beautiful substrings for the first i chars
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
if (s[i - 1] == '0')
continue;
int num = 0; // num of s[i - 1..j - 1]
for (int j = i; j <= n; ++j) {
num = (num << 1) + s[j - 1] - '0';
if (isPowerOfFive(num))
dp[j] = min(dp[j], dp[i - 1] + 1);
}
}
return dp[n] == n + 1 ? -1 : dp[n];
}
private:
bool isPowerOfFive(int num) {
while (num % 5 == 0)
num /= 5;
return num == 1;
}
}; /* code provided by PROGIEZ */
2767. Partition String Into Minimum Beautiful Substrings LeetCode Solution in Java
class Solution {
public int minimumBeautifulSubstrings(String s) {
final int n = s.length();
// dp[i] := the minimum number of beautiful substrings for the first i chars
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
if (s.charAt(i - 1) == '0')
continue;
int num = 0; // num of s[i - 1..j - 1]
for (int j = i; j <= n; ++j) {
num = (num << 1) + s.charAt(j - 1) - '0';
if (isPowerOfFive(num))
dp[j] = Math.min(dp[j], dp[i - 1] + 1);
}
}
return dp[n] == n + 1 ? -1 : dp[n];
}
private boolean isPowerOfFive(int num) {
while (num % 5 == 0)
num /= 5;
return num == 1;
}
} // code provided by PROGIEZ
2767. Partition String Into Minimum Beautiful Substrings LeetCode Solution in Python
class Solution:
def minimumBeautifulSubstrings(self, s: str) -> int:
n = len(s)
# dp[i] := the minimum number of beautiful substrings for the first i chars
dp = [0] + [n + 1] * n
for i in range(1, n + 1):
if s[i - 1] == '0':
continue
num = 0 # the number of s[i - 1..j - 1]
for j in range(i, n + 1):
num = (num << 1) + int(s[j - 1])
if self._isPowerOfFive(num):
dp[j] = min(dp[j], dp[i - 1] + 1)
return -1 if dp[n] == n + 1 else dp[n]
def _isPowerOfFive(self, num: int) -> bool:
while num % 5 == 0:
num //= 5
return num == 1 # code by PROGIEZ
