The testcases are wrong?!

• I've come up with this DP solution:

``````int findMaxForm(vector<string>& strs, int m, int n) {

vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
dp[0][0] = 0;

for(int k = 0; k < strs.size(); k++) {

int ones = 0, zeros = 0;
for(int i = 0; i < (int)strs[k].length(); i++) {
ones += (strs[k][i] == '1');
zeros += (strs[k][i] == '0');
}

for(int i = n; i >= ones; i--) {
for(int j = m; j >= zeros; j--) {
if(dp[i - ones][j - zeros] >= 0) {
dp[i][j] = max(dp[i][j], dp[i - ones][j - zeros] + 1);
}
}
}

}

return max(dp[n][m], 0);
}
``````

But I got wrong answer in this test-case:

``````["10","0001","111001","1","0"]
3
4
``````

How the output is `3`?

In my understanding, output should be `2` (`"111001","0"`).

Then I modified my solution this way which is supposed to be wrong I guess and got accepted:

``````int findMaxForm(vector<string>& strs, int m, int n) {

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

for(int k = 0; k < strs.size(); k++) {

int ones = 0, zeros = 0;
for(int i = 0; i < (int)strs[k].length(); i++) {
ones += (strs[k][i] == '1');
zeros += (strs[k][i] == '0');
}

for(int i = n; i >= ones; i--) {
for(int j = m; j >= zeros; j--) {
dp[i][j] = max(dp[i][j], dp[i - ones][j - zeros] + 1);
}
}

}

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

Now I am thinking test-cases for this problem are wrong. Can anyone please take a look?

• @StefanPochmann can you please explain it?

• Form "10", "1" and "0"?

• @StefanPochmann "10", "1" and "0" consist of total 2 ones and 2 zeros. But in the testcase, m = 3, n = 4.

Am I missing anything?

• Same question with you.

["10","0001","111001","1","0"]
3
4
must return 2, instead of 3

I think most answer posted, found the maximum number of strings can form with less than or equal to m 0s and less than or equal to n 1s.

``````class Solution {
public:
const int INF = ~(1 << 31);
unordered_map<int, int> cache;
int solve(vector<string>& strs, int m, int n, int idx, vector<pair<int,int>> &cnt) {
if(m == 0 && n == 0) return 0;
if(m < 0 || n < 0) return -INF;
if(idx >= strs.size()) return -INF;
int key = idx * 1000000 + m * 1000 + n;
if(cache.count(key)) return cache[key];
return cache[key] = max(solve(strs, m, n, idx+1, cnt), solve(strs, m-cnt[idx].first, n-cnt[idx].second, idx+1, cnt)+1);
}
int findMaxForm(vector<string>& strs, int m, int n) {
vector<pair<int,int>> cnt(strs.size(), {0, 0});
for(int i = 0; i < strs.size(); ++i) {
for(auto const &c: strs[i]) {
if(c == '0') ++cnt[i].first;
else if(c == '1') ++cnt[i].second;
}
}
return max(0, solve(strs, m, n, 0, cnt));
}
};
``````

• I understood now - the question asked to use maximum number of strings from `m` zeros and `n` ones, not necessarily using exactly `m` zeros and `n` ones. Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.