Ones and Zeros problem in Java
Finding the best way to build a subset with particular constraints is the focus of the provided problem, which requires manipulating binary strings. Two non-negative integers (a and b) and an array of binary strings (string) are given to us. The aim is to find the size of the greatest subset of binary strings that prevents the subset's total count of 0s from exceeding a and its total count of 1s from exceeding b.
Example:
Input: string: ["101", "0010", "110", "0011", "000"]
a = 4 , b = 2
Output: The maximum size of the subset with constraints is: 2
Explanation:
The valid subsets include:
{"101", "0011"}
{"0010", "110", "000"}
The largest subset among these is {"101", "0011"} with 3 0's and 2 1's.
The subset {"101", "0011"} has the maximum size while satisfying the constraints (4 zeros and 2 ones).
Approach: Brute Force
The MaxSubsetSizeFinder class finds the largest subset size of binary strings based on 0s and 1s. The findMaxForm() method commences the exploration by calling the recursive helper function findMaxSubsetSize(). This function recursively searches subsets, considering the remaining capabilities for 0s and 1s. The basic case terminates the recursion when the array's end is reached or negative counts of 0s or 1s are encountered. The inclusion or exclusion of each string is determined by constraint fit, with the countZerosOnes() method calculating 0s and 1s.
FileName: MaxSubsetSizeFinder.java
public class MaxSubsetSizeFinder {
// Finds the size of the largest subset of binary strings.
public int findMaxForm(String[] string, int a, int b) {
return findMaxSubsetSize(string, 0, a, b);
}
// Recursive helper function to explore different subsets.
private int findMaxSubsetSize(String[] string, int index, int zerosLeft, int onesLeft) {
if (index == string.length || zerosLeft < 0 || onesLeft < 0) {
return 0;
}
int includeString = 0;
int[] counts = countZerosOnes(string[index]);
// Include the current string if it fits within the constraints.
if (zerosLeft >= counts[0] && onesLeft >= counts[1]) {
includeString = 1 + findMaxSubsetSize(string, index + 1, zerosLeft - counts[0], onesLeft - counts[1]);
}
// Exclude the current string.
int excludeString = findMaxSubsetSize(string, index + 1, zerosLeft, onesLeft);
// Return the maximum size of the subset.
return Math.max(includeString, excludeString);
}
// Counts the occurrences of 0's and 1's in a binary string.
private int[] countZerosOnes(String str) {
int[] counts = new int[2];
for (char c : str.toCharArray()) {
// Increment counts based on the character.
if (c == '0') {
counts[0]++;
} else {
counts[1]++;
}
}
return counts;
}
// Main method to test the solution.
public static void main(String[] args) {
MaxSubsetSizeFinder solution = new MaxSubsetSizeFinder();
String[] string = {"101", "0010", "110", "0011", "000"};
int a = 4, b = 2;
int result = solution.findMaxForm(string, a, b);
System.out.println("The maximum size of the subset with constraints is: " + result);
}
}
Output:
The maximum size of the subset with constraints is: 2
Complexity Analysis: The solution has a time complexity of O(2^(a+b)), where a and b are the sums of zeros and ones in binary strings. The space complexity is O(a*b).
Approach: Using Dynamic Programming
The MaxSubsetFinder1 class uses dynamic programming to efficiently determine the size of the greatest subset of binary strings that satisfies given limitations on the number of 0s and 1s. The findMaxForm() method creates a 2D array, dp, and stores the maximum subset size for various combinations of remaining 0's (a) and 1's (b). It iterates through each binary string in the input array (string) and, using a nested loop, updates the dp array with the number of 0's and 1's in each string. The countZerosOnes() method counts the number of zeroes and ones in a binary string.
FileName: MaxSubsetSizeFinder1.java
public class MaxSubsetSizeFinder1 {
public int findMaxForm(String[] string, int a, int b) {
int[][] dp = new int[a + 1][b + 1];
for (String str : string) {
int[] counts = countZerosOnes(str);
for (int i = a; i >= counts[0]; i--) {
for (int j = b; j >= counts[1]; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - counts[0]][j - counts[1]] + 1);
}
}
}
return dp[a][b];
}
private int[] countZerosOnes(String str) {
int[] counts = new int[2];
for (char c : str.toCharArray()) {
if (c == '0') {
counts[0]++;
} else {
counts[1]++;
}
}
return counts;
}
public static void main(String[] args) {
MaxSubsetSizeFinder1 solution = new MaxSubsetSizeFinder1();
String[] string = {"101", "0010", "110", "0011", "000"};
int a = 4, b = 2;
int result = solution.findMaxForm(string, a, b);
System.out.println("The maximum size of the subset with constraints is: " + result);
}
}
Output:
The maximum size of the subset with constraints is: 2
Complexity Analysis: The solution has a time complexity of O(abn), where a and b are constraints on the counts of 0's and 1's, and n is the length of the input binary string array. The space complexity is O(ab), which reflects the space required for the dynamic programming table.