Ones and Zeroes

Problem Statement

In this problem, we are provided with an array of binary strings called strs along with two integers, m and n. Our goal is to derive the size of the largest subset from the array strs where the total count of the character '0' does not exceed m and the total count of the character '1' does not surpass n. It is crucial to note that a subset, in this context, means a collection of elements that are all found within the original array. The subset should follow the constraints set by m and n regarding the counts of '0's and '1's respectively.

Examples

Example 1

Input:

strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output:

4

Explanation:

The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2

Input:

strs = ["10","0","1"], m = 1, n = 1

Output:

2
**Explanation:** The largest subset is {"0", "1"}, so the answer is 2.

Constraints

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

Approach and Intuition

• The problem can be visualized as a variant of a multi-dimensional knapsack problem. Here, instead of weight, we have two constraints, m and n, which represent the maximum allowable counts of '0's and '1's in the subset.
• The key attributes to consider:
  • The constraints of maximum numbers of 0s (m) and 1s (n) in the subset.
  • The potential of each string in the array contributing to these constraints in varying degrees.

1. Counting Binary Strings: Start by evaluating each string in strs to count how many 0s and 1s they contain. This will help us understand the "weight" each string carries against our limitations m and n.

2. Dynamic Programming (DP) Table Initiation:

   • Create a DP table where dp[i][j] represents the maximum size of the subset possible with at most i numbers of 0s and j numbers of 1s available.

3. Filling Up The DP Table:

   • Iterate through each string and update the DP table in a way to track the maximum size of the subset. For every string, update the table backwards (from m to 0 and n to 0) to make sure each string is only considered once in the subset.
   • For each string, count its zeros and ones. For each pair of (i, j) in the DP table (where i and j are current counts of allowed 0s and 1s): if adding the current string respects the limitations (i.e., doesn't exceed neither m nor n), update the DP value considering the inclusion of the current string.

4. Result Extraction:

   • The value at dp[m][n] will be your result, which indicates the size of the largest subset that fits the criteria.

• Note:
  • DP approach ensures that all potential combinations of strings are considered while respecting the limitations imposed by m and n. This method is effective given the constraints, as direct computation for each possible subset would be computationally expensive given the input sizes.

By applying dynamic programming, this strategy avoids redundant recalculations and offers a systematic approach to building up solutions to larger problems based on solutions to subproblems.

Solutions

public class Solution {
    public int calculateMaxForm(String[] strings, int m, int n) {
        int[][] dpTable = new int[m + 1][n + 1];
        for (String str: strings) {
            int[] counts = getZeroesAndOnes(str);
            for (int zeroCount = m; zeroCount >= counts[0]; zeroCount--)
                for (int oneCount = n; oneCount >= counts[1]; oneCount--)
                    dpTable[zeroCount][oneCount] = Math.max(dpTable[zeroCount - counts[0]][oneCount - counts[1]] + 1, dpTable[zeroCount][oneCount]);
        }
        return dpTable[m][n];
    }
    public int[] getZeroesAndOnes(String s) {
        int[] counter = new int[2];
        for (int i = 0; i < s.length(); i++) {
            counter[s.charAt(i)-'0']++;
        }
        return counter;
    }
}