# Time : O(strs.length * m * n); memory: O(m * n). Bottom-up DP

• Recursive solution with memorization with states (i, m, n) gots memory limit. The below solution is iterativa bottom-up solution. The states are d(position, zeroes, ones). The d[i][j][k] is the maximum answer which we can take for position i by using j zeroes and k ones.
Time complexity: O(strs.length * m * n)
memory complexity: O(m * n)

``````public class Solution {

public int findMaxForm(String[] strs, int m, int n) {
int d[][][] = new int[2][m+1][n+1];

int zeroes = getNumberOfZeroes(strs[0]);
int ones = strs[0].length()-zeroes;

for(int i = zeroes; i<=m; i++){
for(int j = ones; j<=n; j++){
d[0][i][j] = 1;
}
}

for (int i=1; i<strs.length; i++) {
zeroes = getNumberOfZeroes(strs[i]);
ones = strs[i].length()-zeroes;

for (int j=0; j<=m; j++) {
for (int k=0; k<=n; k++) {
d[1][j][k] = d[0][j][k];
if (j-zeroes>=0 && k-ones>=0) {
d[1][j][k] = Math.max(d[0][j-zeroes][k-ones] + 1, d[0][j][k]);
}
}
}

copyCurToPrevState(d, m, n);
}

return d[0][m][n];
}

private void copyCurToPrevState(int d[][][], int m, int n) {
for (int j=0; j<=m; j++) {
for (int k=0; k<=n; k++) {
d[0][j][k] = d[1][j][k];
}
}
}

private int getNumberOfZeroes (String s) {
int counter = 0;
for (int i=0; i<s.length(); i++) {
if (s.charAt(i)=='0') counter++;
}
return counter;
}
}
``````

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