Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
2.1 kB
2
Indexable
Never
class Solution{

    // Function to count number
    // of 0s present in the string
    static int count0(String s)
    {
    	// Stores the count of 0s
    	int count = 0;
    
    	// Iterate over characters of string
    	for (int i = 0; i < s.length(); i++) {
    
    		// If current character is '0'
    		if (s.charAt(i) == '0') {
    			count++;
    		}
    	}
    	return count;
    }
    
    // Recursive Function to find the length of
    // longest subset from given array of strings
    // with at most A 0s and B 1s
    static int solve(String []vec, int A,
    		int B, int idx,
    		int dp[][][])
    {
    	// If idx is equal to N or
    	// A + B is equal to 0
    	if (idx == vec.length || A + B == 0) {
    		return 0;
    	}
    	// If the state is already calculated
    	if (dp[A][B][idx] > 0) {
    		return dp[A][B][idx];
    	}
    
    	// Stores the count of 0's
    	int zero = count0(vec[idx]);
    
    	// Stores the count of 1's
    	int one = vec[idx].length() - zero;
    
    	// Stores the length of longest
    	// by including arr[idx]
    	int inc = 0;
    
    	// If zero is less than A
    	// and one is less than B
    	if (zero <= A && one <= B) {
    		inc = 1
    			+ solve(vec, A - zero,
    					B - one, idx + 1, dp);
    	}
    
    	// Stores the length of longest subset
    	// by excluding arr[idx]
    	int exc = solve(vec, A, B, idx + 1, dp);
    
    	// Assign
    	dp[A][B][idx] = Math.max(inc, exc);
    
    	// Return
    	return dp[A][B][idx];
    }
    
    // Function to find the length of the
    // longest subset of an array of strings
    // with at most A 0s and B 1s
    static int MaxSubsetlength(String []arr,
    					int A, int B){
    	// Stores all Dp-states
    	int dp[][][] = new int[A+1][B+1][arr.length+1];
    	
    	// Return
    	return solve(arr, A, B, 0, dp);
    }
    
    // Driver Code
    public static void main (String[] args) {
    	String arr[] = { "1", "0", "10", "111", "1100", "1000"};
    	int A = 2, B = 2;
    
    	System.out.println(MaxSubsetlength(arr, A, B));
    }
}
Leave a Comment