Ones and Zeroes

The key idea

Each string has a fixed cost: its number of zeros and its number of ones. Choosing strings under two separate budgets (m zeros, n ones) is a 0/1 knapsack with two weight dimensions. Track the best count for every remaining (zeros, ones) budget and update it in reverse so each string is used at most once.

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.

Constraints

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] consists only of digits '0' and '1'.
1 <= m, n <= 100

Examples

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 Output: 4

Input: strs = ["10","0","1"], m = 1, n = 1 Output: 2

Complexity

Time: O(L * m * n) Space: O(m * n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →