Length of longest subset consisting of A 0 s and B 1 s from an array of strings | 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
function count0 ( s ) { let count = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { if ( s [ i ] == ' ' ) { count ++ ; } } return count ; } function solve ( vec , A , B , idx , dp ) { if ( idx == vec . length A + B == 0 ) { return 0 ; } if ( dp [ A ] [ B ] [ idx ] > 0 ) { return dp [ A ] [ B ] [ idx ] ; } let zero = count0 ( vec [ idx ] ) ; let one = vec [ idx ] . length - zero ; let inc = 0 ; if ( zero <= A && one <= B ) { inc = 1 + solve ( vec , A - zero , B - one , idx + 1 , dp ) ; } let exc = solve ( vec , A , B , idx + 1 , dp ) ; dp [ A ] [ B ] [ idx ] = Math . max ( inc , exc ) ; return dp [ A ] [ B ] [ idx ] ; } function MaxSubsetlength ( arr , A , B ) { let dp = new Array ( A + 1 ) ; for ( let i = 0 ; i < A + 1 ; i ++ ) { dp [ i ] = new Array ( B + 1 ) ; for ( let j = 0 ; j < B + 1 ; j ++ ) { dp [ i ] [ j ] = new Array ( arr . length + 1 ) ; for ( let k = 0 ; k < arr . length + 1 ; k ++ ) { dp [ i ] [ j ] [ k ] = 0 ; } } } return solve ( arr , A , B , 0 , dp ) ; } let arr = [ " " , " " , " " ] ; let A = 1 , B = 1 ; document . write ( MaxSubsetlength ( arr , A , B ) ) ;