# Yet another Java DP solution (18ms, beats 100%)

• Time complexity: O(LN + Llg(L)) (L as strs.length)
Space complexity: O(L+N)
Currently beats 100%

``````public class Solution {
private class Count implements Comparable<Count>{
int zero;
int one;
Count(String str) {
zero = 0;
one = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '1') one++;
else zero++;
}
}
public int compareTo(Count b) {
return this.zero - b.zero;
}
}
public int findMaxForm(String[] strs, int m, int n) {
Count[] strings = new Count[strs.length];
for (int i = 0; i < strs.length; i++) {
strings[i] = new Count(strs[i]);
}
Arrays.sort(strings);
int dp[][][] = new int[2][n + 1][2];
int curI = 0;
for (int i = 1; i <= strings.length; i++) {
Count cur = strings[i - 1];
int prevI = curI;
curI ^= 1;
for (int j = 0; j <= n; j++) {
if (j - cur.one >= 0 && (j == 0 ? 0 : dp[prevI][j - 1][1]) + cur.zero <= m && dp[prevI][j - cur.one][0] + 1 > dp[prevI][j][0]) {
dp[curI][j][0] = dp[prevI][j - cur.one][0] + 1;
dp[curI][j][1] = dp[prevI][j - cur.one][1] + cur.zero;
} else {
dp[curI][j][0] = dp[prevI][j][0];
dp[curI][j][1] = dp[prevI][j][1];
}
}
}
return dp[strings.length & 1][n][0];
}
}
``````

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