Untitled
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