https://leetcode.com/problems/ones-and-zeroes/

Q. What's the max number of strings can we pick from and array of strings with limitation of m "0"s and n "1"s.

Example 1:

Input:
 Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3

Output:
 4


Explanation:
 This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Catch:

Knapsackish problem. 3 state DP i, j, k where

• i is string number
• j is no of 0s in that string
• k is no of 1s in that strings
• dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros[in ith string]][k - ones[in ith string]])

Code

public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int no = strs.length;
        int[] zeros = new int[no + 1];
        int[] ones = new int[no + 1];
        int[][][] dp = new int[no + 1][m + 1][n + 1]; //string number, no of 0s, no of ones
        // Store ones and zeros for every string
        for (int i = 1; i <= no; i++) {
            for (int j = 0; j < strs[i - 1].length(); j++) {
                if (strs[i - 1].charAt(j) == '0') {
                    zeros[i]++;
                } else {
                    ones[i]++;
                }
            }
        }
        for (int i = 1; i <= no; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j - zeros[i] >= 0 && k - ones[i] >= 0) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros[i]][k - ones[i]] + 1);
                    }
                }
            }
        }
        return dp[no][m][n];
    }
}