leetcode 474 - Ones and Zeroes

https://leetcode.com/problems/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.

Constraints:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:

int findMaxForm(vector<string>& strs, int m, int n) {
int size = strs.size();
vector<pair<int,int>> counts(size, {0, 0});

for (int i = 0; i < size; i++) {
for (char c : strs[i]) {
if (c == '0')
counts[i].first++;
else
counts[i].second++;
}
}

vector<vector<vector<int>>> memo(m+1, vector<vector<int>>(n+1, vector<int>(size, -1)));

int result = recursive(counts, m, n, size-1, memo);

return result;
}

int recursive(vector<pair<int,int>> &counts, int m, int n, int i,
vector<vector<vector<int>>> &memo) {
if (i < 0) return 0;

if (memo[m][n][i] != -1) return memo[m][n][i];

int total = recursive(counts, m, n, i-1, memo);
if (m >= counts[i].first && n >= counts[i].second)
total = max(total, recursive(counts, m-counts[i].first, n-counts[i].second, i-1, memo) + 1);

memo[m][n][i] = total;

return total;
}
};