56. Ones and Zeroes

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 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.

Solution: (Recursion)

class Solution
{
public:
    int countChar(string &s, char ch)
    {
        int count = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == ch)
            {
                count++;
            }
        }
        return count;
    }

    int findMax(vector<string> &strs, int m, int n, int pos)
    {

        if (pos >= strs.size())
        {
            return 0;
        }

        string k = strs[pos];
        int c1 = countChar(k, '1');
        int c0 = countChar(k, '0');

        int inc = 0, exc = 0;

        if (c1 <= n && c0 <= m)
        {
            inc = 1 + findMax(strs, m - c0, n - c1, pos + 1);
        }

        exc = findMax(strs, m, n, pos + 1);
        return max(inc, exc);
    }

    int findMaxForm(vector<string> &strs, int m, int n)
    {
        int sz = strs.size();

        return findMax(strs, m, n, 0);
    }
};

Solution: (Memonization)

class Solution
{
public:
    int countChar(string &s, char ch)
    {
        int count = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == ch)
            {
                count++;
            }
        }
        return count;
    }

    int findMax(vector<string> &strs, int m, int n, int pos, vector<vector<vector<int>>> &dp)
    {

        if (pos >= strs.size())
        {
            return 0;
        }

        if(dp[pos][m][n]!=-1){
            return dp[pos][m][n];
        };

        string k = strs[pos];
        int c1 = countChar(k, '1');
        int c0 = countChar(k, '0');

        int inc = 0, exc = 0;

        if (c1 <= n && c0 <= m)
        {
            inc = 1 + findMax(strs, m - c0, n - c1, pos + 1, dp);
        }

        exc = findMax(strs, m, n, pos + 1, dp);

        dp[pos][m][n] = max(inc, exc);
        return max(inc, exc);
    }

    int findMaxForm(vector<string> &strs, int m, int n)
    {
        int sz = strs.size();
        vector<vector<vector<int>>> dp(sz + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, -1)));
        return findMax(strs, m, n, 0, dp);
    }
};

Solution: (DP)

class Solution
{
public:
    int countChar(string &s, char ch)
    {
        int count = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == ch)
            {
                count++;
            }
        }
        return count;
    }

    int findMaxForm(vector<string> &strs, int m, int n)
    {
        int sz = strs.size();
        vector<vector<vector<int>>> dp(sz + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));

        for (int i = 1; i <= sz; i++)
        {
            int c1 = countChar(strs[i - 1], '1');
            int c0 = countChar(strs[i - 1], '0');

            for (int j = 0; j <= m; j++)
            {
                for (int k = 0; k <= n; k++)
                {
                    if (k >= c1 && j >= c0)
                    {
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - c0][k - c1] + 1);
                    }
                    else
                    {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }

        return dp[sz][m][n];
    }
};