# Untitled

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));
}
}```