Ones and zeroes

XXX. Find Max Form

Dynamic Programming

Recursion

Memoization

Problem Statement:

Given an array of binary strings strs and two integers m and n, find the maximum number of strings you can form with at most m 0's and n 1's in the strings. Each string can be used at most once.

Algorithm:

This problem can be solved using recursion combined with memoization:

1. Create a 3D memoization table memo[i][m][n], where i is the index of the string being processed, m is the remaining count of 0's, and n is the remaining count of 1's.
2. Define a recursive function dfs that explores two choices for each string: include it in the solution (if possible) or skip it.
3. Use a helper function count to calculate the number of 0's and 1's in each string.
4. Memoize results to avoid redundant computations and speed up the solution.

Complexity:

Time Complexity: O(l * m * n), where l is the number of strings in strs, and m and n are the given constraints. Each state is computed once and stored in the memo table.
Space Complexity: O(l * m * n), for the memoization table and recursion stack.

Java Implementation:

public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] memo = new int[strs.length][m + 1][n + 1];
        return dfs(0, strs, m, n, memo);
    }

    private int dfs(int i, String[] strs, int m, int n, int[][][] memo) {
        if (i == strs.length) return 0; // Base case: no more strings to process

        if (memo[i][m][n] > 0) return memo[i][m][n]; // Return cached result

        int[] count = count(strs[i]); // Count 0's and 1's in the current string

        int take = -1;
        // Try to include the current string if it fits the constraints
        if (m - count[0] >= 0 && n - count[1] >= 0) 
            take = dfs(i + 1, strs, m - count[0], n - count[1], memo) + 1;

        // Skip the current string
        int dont = dfs(i + 1, strs, m, n, memo);

        memo[i][m][n] = Math.max(take, dont); // Store the best result
        return memo[i][m][n];
    }

    private int[] count(String s) {
        int[] count = new int[2];
        for (char c : s.toCharArray()) {
            if (c == '0') count[0]++;
            else if (c == '1') count[1]++;
        }
        return count;
    }
}