[LeetCode] Ones and Zeroes

Problem: You are given an array of binary strings strs and two integers m and n. Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example:

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.

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Approach: This is almost same as Knapsack problem without repetition. We are given the weights (number of zeros and number of ones) and the capacity (m and n) and we need to collect the maximum number of items (include number of strings). 

The only difference here there are two kind of weights and capacities. That means instead of 2 D table, we need to maintain a 3D table where table[i][j][k] will tell how many strings we can take in subarray str[0...i] with at most i zeros and j ones. Obviously table[l][m][n] is our answer. We can fill the table in following way:

• table[i][j][k] =  table[i - 1][j][k]
• IF j >= numOfZeros(strs[i]) AND k >= numOfOnes(strs[i])
• table[i][j][k] = Max(table[i][j][k], table[i - 1][j - numOfZeros(strs[i])][k - numOfOnes(strs[i])]

That's all!

Implementation in C#:

        public static int FindMaxForm(string[] strs, int m, int n)

        {

            int length = strs.Length;

            int[,,] table = new int[length, m + 1, n + 1];            

            for (int i = 0; i < length; ++i)

            {

                int numZeros = strs[i].Count(ch => ch == '0');

                int numOnes = strs[i].Length - numZeros;

                for (int j = m; j >= 0; --j)

                {

                    for (int k = n; k >= 0; --k)

                    {

                        if (i == 0)

                        {

                            if (j - numZeros >= 0 && k - numOnes >= 0)

                            {

                                ++table[i, j, k];

                            }

                        }

                        else

                        {

                            table[i, j, k] = table[i - 1, j, k];

                            if (j - numZeros >= 0 && k - numOnes >= 0)

                            {

                                table[i, j, k] = Math.Max(table[i, j, k], table[i - 1, j - numZeros, k - numOnes] + 1);

                            }

                        }

                    }

                }

            }

            return table[length - 1, m, n];

        }

Complexity: O(n^3)