Ones and Zeroes Problem

Problem

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.

Examples

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.

Solution

Method 1 – Dynamic Programming (Knapsack)

Intuition

Use dynamic programming to select the largest subset of strings such that the total number of 0's and 1's does not exceed m and n, similar to the 2D knapsack problem.

Approach

1. For each string, count the number of 0's and 1's.
2. Use a DP table dp[i][j] where dp[i][j] is the largest subset size with at most i 0's and j 1's.
3. For each string, update the DP table in reverse to avoid overcounting.

Code

C++

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for (auto& s : strs) {
            int zeros = count(s.begin(), s.end(), '0');
            int ones = s.size() - zeros;
            for (int i = m; i >= zeros; --i) {
                for (int j = n; j >= ones; --j) {
                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
};

Go

func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int, m+1)
    for i := range dp { dp[i] = make([]int, n+1) }
    for _, s := range strs {
        zeros, ones := 0, 0
        for _, c := range s {
            if c == '0' { zeros++ } else { ones++ }
        }
        for i := m; i >= zeros; i-- {
            for j := n; j >= ones; j-- {
                if dp[i-zeros][j-ones]+1 > dp[i][j] {
                    dp[i][j] = dp[i-zeros][j-ones]+1
                }
            }
        }
    }
    return dp[m][n]
}

Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            for (int i = m; i >= zeros; --i) {
                for (int j = n; j >= ones; --j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
}

Kotlin

class Solution {
    fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
        val dp = Array(m+1) { IntArray(n+1) }
        for (s in strs) {
            val zeros = s.count { it == '0' }
            val ones = s.length - zeros
            for (i in m downTo zeros) {
                for (j in n downTo ones) {
                    dp[i][j] = maxOf(dp[i][j], dp[i-zeros][j-ones]+1)
                }
            }
        }
        return dp[m][n]
    }
}

Python

class Solution:
    def findMaxForm(self, strs: list[str], m: int, n: int) -> int:
        dp = [[0]*(n+1) for _ in range(m+1)]
        for s in strs:
            zeros = s.count('0')
            ones = len(s) - zeros
            for i in range(m, zeros-1, -1):
                for j in range(n, ones-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
        return dp[m][n]

Rust

impl Solution {
    pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
        let m = m as usize;
        let n = n as usize;
        let mut dp = vec![vec![0; n+1]; m+1];
        for s in strs.iter() {
            let zeros = s.chars().filter(|&c| c == '0').count();
            let ones = s.len() - zeros;
            for i in (zeros..=m).rev() {
                for j in (ones..=n).rev() {
                    dp[i][j] = dp[i][j].max(dp[i-zeros][j-ones]+1);
                }
            }
        }
        dp[m][n]
    }
}

TypeScript

class Solution {
    findMaxForm(strs: string[], m: number, n: number): number {
        const dp: number[][] = Array.from({length: m+1}, () => Array(n+1).fill(0));
        for (const s of strs) {
            const zeros = s.split('').filter(c => c === '0').length;
            const ones = s.length - zeros;
            for (let i = m; i >= zeros; --i) {
                for (let j = n; j >= ones; --j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
}

Complexity

• ⏰ Time complexity: O(L * m * n)
  • For each string (L), we update a DP table of size m x n, resulting in O(L * m * n) operations.
• 🧺 Space complexity: O(m * n)
  • The DP table stores the largest subset size for each possible number of 0's and 1's.