Leetcode 2767: Partition String Into Minimum Beautiful Substrings
Given a binary string ’s’, partition it into substrings such that each substring represents a power of 5 in binary form and does not contain leading zeros. Return the minimum number of such partitions, or -1 if impossible.
Problem
Approach
Steps
Complexity
Input: The input consists of a single binary string 's'.
Example: Input: s = '1101'
Constraints:
• 1 <= s.length <= 15
• s[i] is either '0' or '1'.
Output: Return the minimum number of partitions such that each substring meets the specified criteria. If no valid partition exists, return -1.
Example: Output: 2 for Input: s = '1101'
Constraints:
• Output must be an integer, representing the minimum number of partitions or -1 if invalid.
Goal: To minimize the number of substrings while ensuring each substring represents a power of 5 and does not have leading zeros.
Steps:
• Iterate through the binary string and check all possible substrings.
• For each substring, check if it is a valid binary representation of a power of 5.
• Use dynamic programming to track the minimum partitions for each prefix of the string.
Goal: Ensure the solution works within the constraints of string length and binary properties.
Steps:
• 1 <= s.length <= 15
• s[i] is either '0' or '1'.
Assumptions:
• All substrings must represent numbers greater than zero.
• Leading zeros in substrings invalidate them.
• Input: Input: s = '1101'
• Explanation: The string can be split into ['110', '1'], where both parts are valid binary representations of powers of 5.
• Input: Input: s = '0001'
• Explanation: The string cannot be partitioned into valid substrings as all parts have leading zeros.
Approach: Dynamic programming approach to minimize partitions while validating binary substrings as powers of 5.
Observations:
• Binary strings can be parsed into integers to check if they are powers of 5.
• Leading zeros are invalid, so such substrings are not considered.
• Dynamic programming can efficiently find the minimum number of valid partitions.
Steps:
• Initialize a dp array where dp[i] represents the minimum partitions for the substring s[0:i].
• Iterate through all possible substrings of 's'.
• Check if a substring is valid by verifying it does not have leading zeros and is a power of 5.
• Update the dp array with the minimum partitions required.
Empty Inputs:
• The constraints ensure the input string is not empty.
Large Inputs:
• The maximum length of the string is 15, so edge cases with maximum length must be handled efficiently.
Special Values:
• Strings with only zeros ('0000') or invalid patterns should return -1.
Constraints:
• The binary string must be partitioned into contiguous, valid substrings.
int minimumBeautifulSubstrings(string s) {
int n = s.length();
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') continue;
for (int j = i, cur = 0; j < n; j++) {
cur = cur * 2 + s[j] - '0';
if (15625 % cur == 0)
dp[j + 1] = min(dp[j + 1], dp[i] + 1);
}
}
return dp[n] > n ? -1 : dp[n];
}
1 : Function Definition
int minimumBeautifulSubstrings(string s) {
Defines the function `minimumBeautifulSubstrings`, which takes a binary string `s` and returns the minimum number of beautiful substrings or `-1` if it's impossible.
2 : Calculate String Length
int n = s.length();
Calculates the length of the input string `s` and stores it in the variable `n`.
3 : Initialize DP Array
vector<int> dp(n + 1, n + 1);
Initializes a dynamic programming (DP) array `dp` of size `n + 1` where each entry represents the minimum number of beautiful substrings up to that position in the string. Initially, all values are set to `n + 1`.
4 : Base Case
dp[0] = 0;
Sets the base case: `dp[0]` is 0, indicating no substrings are needed for an empty string.
5 : Iterate Over String
for (int i = 0; i < n; i++) {
Starts a loop to iterate over each character in the input string `s`.
6 : Skip Zeros
if (s[i] == '0') continue;
If the current character is '0', skips the rest of the loop and moves to the next character.
7 : Inner Loop
for (int j = i, cur = 0; j < n; j++) {
Starts an inner loop to iterate from the current position `i` to the end of the string, calculating the binary value of the substring starting at `i`.
8 : Update Current Value
cur = cur * 2 + s[j] - '0';
Updates the current binary value `cur` by shifting it left by one bit (multiply by 2) and adding the current character (`s[j]`) to it. The subtraction of `'0'` converts the character to its integer value (0 or 1).
9 : Check Divisibility
if (15625 % cur == 0)
Checks if the current binary value `cur` is divisible by 15625 (the divisor for beautiful substrings).
10 : Update DP Array
dp[j + 1] = min(dp[j + 1], dp[i] + 1);
If the current binary value is divisible by 15625, updates the DP array at index `j + 1` to reflect the minimum number of beautiful substrings by adding 1 to the DP value at index `i`.
11 : Return Result
return dp[n] > n ? -1 : dp[n];
Returns the minimum number of beautiful substrings, which is stored in `dp[n]`. If no valid result is found (i.e., `dp[n]` is greater than `n`), it returns `-1`.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: Iterating through substrings and checking validity contributes to the quadratic complexity.
Best Case: O(n)
Worst Case: O(n)
Description: Space complexity is dominated by the dp array storing results for substrings.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus