Length of longest subset consisting of A 0 s and B 1 s from an array of strings | C ++ program for the above approach ; Function to count number of 0 s present in the string ; Stores the count of 0 s ; Iterate over characters of string ; If current character is '0' ; Recursive Function to find the length of longest subset from given array of strings with at most A 0 s and B 1 s ; If idx is equal to N or A + B is equal to 0 ; If the state is already calculated ; Stores the count of 0 's ; Stores the count of 1 's ; Stores the length of longest by including arr [ idx ] ; If zero is less than A and one is less than B ; Stores the length of longest subset by excluding arr [ idx ] ; Assign ; Return ; Function to find the length of the longest subset of an array of strings with at most A 0 s and B 1 s ; Stores all Dp - states ; Return ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count0 ( string s ) { int count = 0 ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) { if ( s [ i ] == '0' ) { count ++ ; } } return count ; } int solve ( vector < string > vec , int A , int B , int idx , vector < vector < vector < int > > > & dp ) { if ( idx == vec . size ( ) A + B == 0 ) { return 0 ; } if ( dp [ A ] [ B ] [ idx ] > 0 ) { return dp [ A ] [ B ] [ idx ] ; } int zero = count0 ( vec [ idx ] ) ; int one = vec [ idx ] . size ( ) - zero ; int inc = 0 ; if ( zero <= A && one <= B ) { inc = 1 + solve ( vec , A - zero , B - one , idx + 1 , dp ) ; } int exc = solve ( vec , A , B , idx + 1 , dp ) ; dp [ A ] [ B ] [ idx ] = max ( inc , exc ) ; return dp [ A ] [ B ] [ idx ] ; } int MaxSubsetlength ( vector < string > arr , int A , int B ) { vector < vector < vector < int > > > dp ( A + 1 , vector < vector < int > > ( B + 1 , vector < int > ( arr . size ( ) + 1 , 0 ) ) ) ; return solve ( arr , A , B , 0 , dp ) ; } int main ( ) { vector < string > arr = { "1" , "0" , "10" } ; int A = 1 , B = 1 ; cout << MaxSubsetlength ( arr , A , B ) ; return 0 ; }