Ones and Zeroes

Given an array, strs, with strings consisting of only 0s and 1s. Also two integers m and n.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Example 1:

Input: strs = ["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".

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

Constraints:

• 1 <= strs.length <= 600

• 1 <= strs[i].length <= 100

• strs[i] consists only of digits '0' and '1'.

• 1 <= m, n <= 100

/*
The problem can be interpreted as: What's the max number of str can we pick from strs with limitation of m "0"s and n "1"s.
Thus we can define dp[i][j] stands for max number of str can we pick from strs with limitation of i "0"s and j "1"s.
For each str, assume it has a "0"s and b "1"s, we update the dp array iteratively and set dp[i][j] = Math.max(dp[i][j], dp[i - a][j - b] + 1). So at the end, dp[m][n] is the answer.
*/

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] list = new int[strs.length][];
        int index = 0;
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray())
                if (c == '0')
                    zeros++;
                else
                    ones++;
            list[index++] = new int[] { zeros, ones };
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int[] x : list) {
            for (int i = m; i - x[0] >= 0; i--)
                for (int j = n; j - x[1] >= 0; j--)
                    dp[i][j] = Math.max(1 + dp[i - x[0]][j - x[1]], dp[i][j]);
        }
        return dp[m][n];
    }
}