Last updated on January 5th, 2025 at 12:58 am
Here, we see the Ones and Zeroes LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic-Programming
Companies
Level of Question
Medium
Ones and Zeroes LeetCode Solution
Table of Contents
1. Problem Statement
You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
Example 1:
Input: strs = [“10″,”0001″,”111001″,”1″,”0”], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0’s and 3 1’s is {“10”, “0001”, “1”, “0”}, so the answer is 4. Other valid but smaller subsets include {“0001”, “1”} and {“10”, “1”, “0”}. {“111001”} is an invalid subset because it contains 4 1’s, greater than the maximum of 3.
Example 2:
Input: strs = [“10″,”0″,”1”], m = 1, n = 1
Output: 2
Explanation: The largest subset is {“0”, “1”}, so the answer is 2.
2. Coding Pattern Used in Solution
The provided code implements the 0/1 Knapsack dynamic programming pattern. This pattern is used to solve problems where you need to maximize or minimize a value (e.g., profit, count, etc.) under certain constraints (e.g., weight, capacity, etc.). In this case, the problem is to maximize the number of strings that can be formed using at most m zeros and n ones.
3. Code Implementation in Different Languages
3.1 Ones and Zeroes C++
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(string str : strs){
int one = 0;
int zero = 0;
for(char c : str){
if(c == '1')
one++;
else
zero++;
}
for(int i = m; i >= zero; i--){
for(int j = n; j >= one; j--){
if(one <= j && zero <= i)
dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);
}
}
}
return dp[m][n];
}
};
3.2 Ones and Zeroes Java
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for(String str : strs){
int one = 0;
int zero = 0;
for(char c : str.toCharArray()){
if(c == '1')
one++;
else
zero++;
}
for(int i = m; i >= zero; i--){
for(int j = n; j >= one; j--){
if(one <= j && zero <= i)
dp[i][j] = Math.max(dp[i][j],dp[i - zero][j - one] + 1);
}
}
}
return dp[m][n];
}
}
3.3 Ones and Zeroes JavaScript
var findMaxForm = function(strs, m, n) {
let dp = Array.from({length:m+1},() => new Uint8Array(n+1))
for (let i = 0; i < strs.length; i++) {
let str = strs[i], zeros = 0, ones = 0
for (let j = 0; j < str.length; j++)
str.charAt(j) === "0" ? zeros++ : ones++
for (let j = m; j >= zeros; j--)
for (let k = n; k >= ones; k--)
dp[j][k] = Math.max(dp[j][k], dp[j-zeros][k-ones] + 1)
}
return dp[m][n]
};
3.4 Ones and Zeroes Python
class Solution(object):
def findMaxForm(self, strs, m, n):
dp = [[0] * (n+1) for _ in range(m+1)]
for str in strs:
one = 0
zero = 0
for c in str:
if c == '1':
one += 1
else:
zero += 1
for i in range(m, zero-1, -1):
for j in range(n, one-1, -1):
if one <= j and zero <= i:
dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1)
return dp[m][n]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(L * (m * n)) | O(m*n) |
| Java | O(L * (m * n)) | O(m*n) |
| JavaScript | O(L * (m * n)) | O(m*n) |
| Python | O(L * (m * n)) | O(m*n) |
where, L is the number of strings in strs.
- The code uses a bottom-up dynamic programming approach to solve the problem.
- The reverse iteration over the
dptable ensures that each string is considered only once, adhering to the 0/1 Knapsack principle. - The solution is efficient for moderate values of
m,n, andL, but it may become computationally expensive for very large inputs due to theO(L * m * n)time complexity.