Sponsored
Sponsored
This problem can be approached using a dynamic programming strategy similar to the knapsack problem. For each binary string, calculate the number of 0's and 1's it contains. Then, use a DP table to keep track of the maximum subset size you can achieve with a given count of 0's and 1's. We'll fill this table by iterating over each string and attempting to include it in our subset if the current capacity allows. Update the DP table in a reverse manner to avoid overwriting results prematurely.
Time Complexity: O(strsSize * m * n) where strsSize is the number of binary strings.
Space Complexity: O(m * n) for storing the DP table.
1import java.util.List;
2
3class Solution {
4 public int findMaxForm(List<String> strs, int m, int n) {
5 int[][] dp = new int[m + 1][n + 1];
6 for (String s : strs) {
7 int zeros = (int) s.chars().filter(c -> c == '0').count();
8 int ones = s.length() - zeros;
9 for (int i = m; i >= zeros; i--) {
10 for (int j = n; j >= ones; j--) {
11 dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
12 }
13 }
14 }
15 return dp[m][n];
16 }
17}The Java solution employs an integer two-dimensional array to store the possible outcomes just like the C/C++ solutions. The core idea is preserved, where zeros and ones in each binary string are counted using Java's streaming API to make it concise. After computing the counts, the DP table is updated in a loop from back to front to ensure existing values are not overwritten.
The problem can also be tackled using a recursive function with memoization to store already computed results and avoid redundant calculations. This approach uses recursion to consider two choices for each string - either include it in the subset or not, based on the available capacity for zeros and ones. By storing intermediate results, we can significantly reduce the number of recursive calls needed, thus optimizing the process.
Time Complexity: O(strsSize * m * n) due to memoization.
Space Complexity: O(strsSize * m * n) for the memoization table.
1
The Java solution uses a hashmap for memoization. The helper function calculates whether to include or exclude the strings at a given index from the subset. Memoization maintains the previous computations to improve efficiency, allowing the recursive exploration of possibilities within the constraints of zeros and ones.