Find the length of the longest subset consisting of A 0s and B 1s from a string array

In this problem, we need to find the longest subset that contains at most A 0s and B1s. All we need to do is find all possible subsets using array elements and find the longest subset that contains at most A 0 and B1 .

In this tutorial, first, we will learn the recursive method to solve the problem. After that, we will use dynamic programming methods to optimize the code.

Problem Statement - We are given an array containing N binary strings. Additionally, we are given the A and B integers. We need to create the longest subset using the given binary string such that it does not contain more than A 0 and B1.

Example

Input –  arr = {"101", "0", "101", "0", "1"}, A = 2, B = 1

Output – 3

illustrate

The longest subset is { "0", "0", "1"}, containing 2 0s and 1 1.

Input –  arr = {"0", "101", "0", "1"}, A = 3, B = 3

Output – 3

illustrate

The longest subset is {"0", "101", "0", "1"}, 3 0s and 3 1s.

method 1

In this section, we will learn a simple method using recursion. We will construct all possible subsets using the array elements and find the longest subset containing A 0 and B 1 .

algorithm

• Step 1 - Define countZeros() function to count the total number of zeros in a given binary string.

• Step 1.1 - Initialize the "count" variable to zero.

• Step 1.2 - Use a for loop to iterate through the string.

• Step 1.3 - If the character at the i-th index is "0", then increase the value of "cnt" by 1.

• Step 1.2 - Return the value of the "cnt" variable.

• Step 2 - getMaxSubsetLen() returns an integer value and takes the vector arr, int A, int B, and index as arguments.

• Step 3 - Define the base case within the function. Returns 0 if the index is equal to the size of the vector, or if the values ​​of A and B are both zero.

• Step 4 - Now, count the total number of zeros in the string at index.

• Step 5 - Subtract the total number of 1's from the string length to get the total number of 1's.

• Step 6 - Initialize the "first" variable to 0.

• Step 7 - Contains the current binary string if the total number of 0 and 1 is less than A and B respectively. Stores 1 the return value of a recursive function call. When making a recursive call, 0 and 1 are subtracted from A and B.

• Step 8 - Exclude the current string and store the resulting value in the "second" variable.

• Step 9 - Return the maximum value of the first and second.

Example

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> arr, int A, int B, int index){

   // base case
   // if all the strings are traversed, or A + B becomes 0
   if (index == arr.size() || A + B == 0){
      return 0;
   }
   
   // total number of 0's in arr[index] string
   int zero = countZeros(arr[index]);
   
   // total number of 1's in arr[index] string
   int one = arr[index].size() - zero;
   
   // Stores the length of the subset, if arr[i] is included.
   int first = 0;
   
   // if the number of 0's and 1's in arr[index] is less than or equal to A and B, respectively, then include the string
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(arr, A - zero, B - one, index + 1);
   }
   
   // Stores the length of the subset, if arr[i] is not included.
   int second = getMaxSubsetLen(arr, A, B, index + 1);
   
   // return the maximum of the first and second
   return max(first, second);
}

// Driver Code
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " <<getMaxSubsetLen(arr, A, B, 0);
   return 0;
}

Output

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Time complexity - O(2N), since we find all possible subsets using N array elements.

Space complexity - O(1)

Method 2

We have optimized the above method in this section. We use dynamic programming methods to solve this problem. It stores the result of the previous state to reduce the time complexity of the problem.

algorithm

• Step 1 - Define countZeros() function to count the total number of zeros in a specific binary string, just like we did in the above method.

• Step 2 - Create a 3-dimensional vector of size A x B x N to store the result of the previous state. In the list, we will store the length of the subset at index "I" when the total 0 equals A and 1 equals B. Additionally, pass it as an argument to the getMaxSubsetLen() function.

• Step 3 - Define the base case as we did in the above method.

• Step 4 - If the value of dpTable[A][B][index] is greater than 0, it means that the status has been calculated and its value is returned.

• Step 5 - Count the total number of 0s and 1s in the current string.

• Step 6 - Get the resulting value including and excluding the current string.

• Step 7 - After using the max() function to get the maximum value of the first and second and storing it in dpTable[A][B][index] return

Example

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> array, int A, int B, int index, vector<vector<vector<int>>> &dpTable){

   // base case
   if (index == array.size() || A + B == 0){
      return 0;
   }
   
   // return if already calculated
   if (dpTable[A][B][index] > 0){
      return dpTable[A][B][index];
   }
   
   // total number of 0's in the current string
   int zero = countZeros(array[index]);
   
   // total number of 1's in the current string
   int one = array[index].size() - zero;
   
   // to store the length of the subset can be formed by including the current string
   int first = 0;
   
   // if the total number of 0's and 1's in the current string is less than or equal to A and B, respectively
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(array, A - zero, B - one, index + 1, dpTable);
   }
   
   // to store the length of the subset can be formed by excluding the current string
   int second = getMaxSubsetLen(array, A, B, index + 1, dpTable);
   
   // store the maximum of the first and second, and return
   return dpTable[A][B][index] = max(first, second);
}
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   vector<vector<vector<int>>> dpTable(A + 1, vector<vector<int>>(B + 1, vector<int>(arr.size() + 1, 0)));
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " << getMaxSubsetLen(arr, A, B, 0, dpTable);
   return 0;
}

Output

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Time complexity - O(A*B*N), since we need to populate the 3D list to get the result.

Space Complexity - O(A*B*N) because we use 3D lists for dynamic programming method.

The above is the detailed content of Find the length of the longest subset consisting of A 0s and B 1s from a string array. For more information, please follow other related articles on the PHP Chinese website!