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.

Solution Approach

Expected Time complexity: $O(l*m*n)$

Click - to see solution code

C++

class Solution {
   public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int siz = strs.size();

        vector<vector<int>> ans(m + 1, vector<int>(n + 1));

        for (auto i : strs) {
            int cnt1 = 0, cnt2 = 0;
            cnt1 = count(i.begin(), i.end(), '1');
            cnt2 = i.length() - cnt1;

            for (int j = m; j >= cnt2; j--) {
                for (int k = n; k >= cnt1; k--) {
                    ans[j][k] = max(ans[j][k], ans[j - cnt2][k - cnt1] + 1);
                }
            }
        }
        return ans[m][n];
    }
};