Length of longest subset consisting of A 0 s and B 1 s from an array of strings | Java 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
import java . io . * ; class GFG { static int count0 ( String s ) { int count = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s . charAt ( i ) == '0' ) { count ++ ; } } return count ; } static int solve ( String [ ] vec , int A , int B , int idx , int dp [ ] [ ] [ ] ) { if ( idx == vec . length 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 ] . length ( ) - 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 ] = Math . max ( inc , exc ) ; return dp [ A ] [ B ] [ idx ] ; } static int MaxSubsetlength ( String [ ] arr , int A , int B ) { int dp [ ] [ ] [ ] = new int [ A + 1 ] [ B + 1 ] [ arr . length + 1 ] ; return solve ( arr , A , B , 0 , dp ) ; } public static void main ( String [ ] args ) { String arr [ ] = { "1" , "0" , "10" } ; int A = 1 , B = 1 ; System . out . println ( MaxSubsetlength ( arr , A , B ) ) ; } }