Ones and Zeroes LeetCode Solution

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

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.

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];
    }
};Code language: PHP (php)

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];
    }
}Code language: JavaScript (javascript)

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]
};Code language: JavaScript (javascript)

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]
Scroll to Top