text: Length of longest subset consisting of A 0 s and B 1 s from an array of strings | Set 2 | C ++ program for the above approach ; Function to find the length of the longest subset of an array of strings with at most A 0 s and B 1 s ; Initialize a 2D array with its entries as 0 ; Traverse the given array ; Store the count of 0 s and 1 s in the current string ; Iterate in the range [ A , zeros ] ; Iterate in the range [ B , ones ] ; Update the value of dp [ i ] [ j ] ; Print the result ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int MaxSubsetlength ( vector < string > 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 < string > arr = { "1" , "0" , "0001" , "10" , "111001" } ; int A = 5 , B = 3 ; cout << MaxSubsetlength ( arr , A , B ) ; return 0 ; }