#### clueless coding// TODO: be smarter

Cracking the Coding Interview Elements of Programming Interviews Programming Interviews Exposed # LeetCode Ones and Zeroes: CPP Solution

## TL;DR Code Solution

``````    int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> memo(m+1, vector<int>(n+1, 0));
int numZeroes, numOnes;

for (auto &s : strs) {
numZeroes = numOnes = 0;
// count number of zeroes and ones in current string
for (auto c : s) {
if (c == '0')
numZeroes++;
else if (c == '1')
numOnes++;
}

// memo[i][j] = the max number of strings that can be formed with i 0's and j 1's
// from the first few strings up to the current string s
// Catch: have to go from bottom right to top left
// Why? If a cell in the memo is updated(because s is selected),
// we should be adding 1 to memo[i][j] from the previous iteration (when we were not considering s)
// If we go from top left to bottom right, we would be using results from this iteration => overcounting
for (int i = m; i >= numZeroes; i--) {
for (int j = n; j >= numOnes; j--) {
memo[i][j] = max(memo[i][j], memo[i - numZeroes][j - numOnes] + 1);
}
}
}
return memo[m][n];
}

``````