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.
1class Solution:
2 def findMaxForm(self, strs, m, n):
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 for s in strs:
5 zeros = s.count('0')
6 ones = len(s) - zeros
7 for i in range(m, zeros - 1, -1):
8 for j in range(n, ones - 1, -1):
9 dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
10 return dp[m][n]In Python, the DP strategy is kept intact, using a list to store maximum subset sizes for varying counts of zeros and ones. The count method succinctly calculates zeros, and len is used to deduce the number of ones. A reversed iteration of the DP table manages how strings are considered for inclusion in the subsets without overwriting unconsidered values.
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#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
vector<string> strsLocal;
unordered_map<string, int> memo;
string getKey(int index, int m, int n) {
return to_string(index) + ',' + to_string(m) + ',' + to_string(n);
}
int helper(int index, int m, int n) {
if (index < 0) return 0;
string key = getKey(index, m, n);
if (memo.find(key) != memo.end()) {
return memo[key];
}
int zeros = count(strsLocal[index].begin(), strsLocal[index].end(), '0');
int ones = strsLocal[index].size() - zeros;
int exclude = helper(index - 1, m, n);
int include = 0;
if (m >= zeros && n >= ones) {
include = 1 + helper(index - 1, m - zeros, n - ones);
}
memo[key] = max(exclude, include);
return memo[key];
}
public:
int findMaxForm(vector<string>& strs, int m, int n) {
strsLocal = strs;
memo.clear();
return helper(strs.size() - 1, m, n);
}
};In the C++ version, an unordered_map is used for memoization by storing states as strings. The memoization prevents repeated calculations, optimizing the recursive exploration of subsets. The recursive function considers all configurations and stores results to avoid recalculating for the same inputs.