Leetcode Ones and Zeroes problem solution

In this Leetcode Ones and Zeroes problem solution 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.

Leetcode Ones and Zeroes problem solution

Topics we are covering

Problem solution in Python.

from collections import Counter
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        weights = []
        for st in strs:
            counter = Counter(st)
            weights.append((counter.get("0", 0), counter.get("1", 0)))
        self.visited = {}
        return self.recursiveWithMemo(strs, weights, len(strs) - 1, (m, n))
    
    # Brute Force Recursive Solution
    def recursiveWithoutMemo(self, strs, weights, index, wt):
        if wt == (0, 0) or index < 0: return 0
        else:
            curr = weights[index]
            if curr[0] <= wt[0] and curr[1] <= wt[1]:
                return max(
                    1 + self.recursiveWithoutMemo(strs, weights, index - 1, (wt[0] - curr[0], wt[1] - curr[1])),
                    self.recursiveWithoutMemo(strs, weights, index - 1, wt)
                )
            else:
                return self.recursiveWithoutMemo(strs, weights, index - 1, wt)

Problem solution in Java.

public int findMaxForm(String[] strs, int m, int n) {
        Arrays.sort(strs, new Comparator<String>(){
            public int compare(String s1, String s2) {
                int val = s1.length() - s2.length();
                if(val != 0)
                    return val;
                return s1.compareTo(s2);
            }
        });
        int result = 0;
        for(int i = 0; i < strs.length; i++)
            result = Math.max(result, dfs(strs, m, n, i));
        return result;
    }
    public int dfs(String[] strs, int m, int n, int start) {
        boolean flag;
        int result = 0, mm, nn;
        for(; start < strs.length; start++) {
            char[] c = strs[start].toCharArray();
            flag = true;
            if(c.length > m + n)
                break;
            mm = m;
            nn = n;
            for(int i = 0; i < c.length; i++) {
                if(c[i] == '0' && m > 0)
                    m--;
                else if(c[i] == '1' && n > 0)
                    n--;
                else {
                    flag = false;
                    break;
                }
            }
            if(flag)
                result++;
            else {
                m = mm;
                n = nn;
            }
        }
        return result;
    }

Problem solution in C++.

pair<int, int> countChars(string& str) {
    int ones = 0, zeros = 0;
    for (auto c : str) {
        if (c == '0') {
            zeros++;
        } else {
            ones++;
        }
    }
    return {zeros, ones};
}
int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<vector<int>>> dp(strs.size() + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
    for (int i = 0; i < strs.size(); i++) {
        auto counts = countChars(strs[i]);
        int ones = counts.second, zeros = counts.first;
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (zeros <= j && ones <= k) {
                    dp[i + 1][j][k] = max(dp[i][j][k], 1 + dp[i][j - zeros][k - ones]);
                } else {
                    dp[i + 1][j][k] = dp[i][j][k];
                }
            }
        }
    }
    return dp[strs.size()][m][n];
}

coding problems solutions