Last updated on October 5th, 2024 at 04:47 pm

Here, We see Ones and Zeroes LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Ones and Zeroes LeetCode Solution

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.

1. Ones and Zeroes LeetCode Solution 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];
    }
};

2. Ones and Zeroes LeetCode Solution 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. Ones and Zeroes Solution 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]
};

4. Ones and Zeroes Solution 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]