# Length of longest subset consisting of A 0s and B 1s from an array of strings | Set 2

Length of longest subset consisting of A 0s and B 1s from an array of strings | Set 2Given an array arr[] consisting of N binary strings, and two integers A and B, the task is to find the length of the longest subset consisting of at most A 0s and B 1s.Examples:Input: arr[] = {“1”, “0”, “0001”, “10”, “111001”}, A = 5, B = 3Output: 4Explanation: One possible way is to select the subset {arr[0], arr[1], arr[2], arr[3]}.Total number of 0s and 1s in all these strings are 5 and 3 respectively.Also, 4 is the length of the longest subset possible.Input: arr[] = {“0”, “1”, “10”}, A = 1, B = 1Output: 2Explanation: One possible way is to select the subset {arr[0], arr[1]}.Total number of 0s and 1s in all these strings is 1 and 1 respectively.Also, 2 is the length of the longest subset possible.Naive Approach: Refer to the previous post of this article for the simplest approach to solve the problem. Time Complexity: O(2N)Auxiliary Space: O(1)Dynamic Programming Approach: Refer to the previous post of this article for the Dynamic Programming approach. Time Complexity: O(N*A*B)Auxiliary Space: O(N * A * B)Space-Optimized Dynamic Programming Approach: The space complexity in the above approach can be optimized based on the following observations:Initialize a 2D array, dp[A][B], where dp[i][j] represents the length of the longest subset consisting of at most i number of 0s and j number of 1s.To optimize the auxiliary space from the 3D table to the 2D table, the idea is to traverse the inner loops in reverse order.This ensures that whenever a value in dp[][] is changed, it will not be needed anymore in the current iteration.Therefore, the recurrence relation looks like this:dp[i][j] = max (dp[i][j], dp[i – zeros][j – ones] + 1)where zeros is the count of 0s and ones is the count of 1s in the current iteration.Follow the steps below to solve the problem:Initialize a 2D array, say dp[A][B] and initialize all its entries as 0.Traverse the given array arr[] and for each binary string perform the following steps:After completing the above steps, print the value of dp[A][B] as the result.Below is the implementation of the above approach:C++#include using namespace std;int MaxSubsetlength(vector arr, int A, int B){ int dp[A + 1][B + 1]; memset(dp, 0, sizeof(dp)); for (auto& str : arr) { int zeros = count(str.begin(), str.end(), ‘0’); int ones = count(str.begin(), str.end(), ‘1’); for (int i = A; i >= zeros; i–) for (int j = B; j >= ones; j–) dp[i][j] = max( dp[i][j], dp[i – zeros][j – ones] + 1); } return dp[A][B];}int main(){ vector arr = { “1”, “0”, “0001”, “10”, “111001” }; int A = 5, B = 3; cout = zeros; i–) for(int j = B; j >= ones; j–) dp[i][j] = Math.max( dp[i][j], dp[i – zeros][j – ones] + 1); } return dp[A][B];}public static void main(String[] args){ String arr[] = { “1”, “0”, “0001”, “10”, “111001” }; int A = 5, B = 3; System.out.println(MaxSubsetlength(arr, A, B));}}Output: 4Time Complexity: O(N * A * B)Auxiliary Space: O(A * B)Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.