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

c++

class Solution {
    int dp[101][101];
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int res = 0;
        memset(dp, 0, sizeof dp);
        for(auto& str : strs) {
            int zero = 0, one = 0;
            for(auto& ch : str) {
                if(ch == '0') zero++;
                else one++;
            }
            if(zero > m or one > n) continue;
            for(int i = m - zero; i >= 0; i--) {
                for(int j = n - one; j >= 0; j--) {
                    dp[i+zero][j+one] = max(dp[i+zero][j+one], 1 + dp[i][j]);
                    res = max(res, dp[i+zero][j+one]);
                }
            }
            
            dp[zero][one] = max(dp[zero][one], 1);
            res = max(res, dp[zero][one]);
        }
        return res;
    }
};