hardDynamic Programming 2DPure DSA~30 min
Most Strings Within a Zero and One Budget
You select binary feature flags (strings of 0s and 1s) to ship, but your build budget caps the total number of 0-bits and 1-bits you can include. Maximize how many strings you ship.
Problem
Given an array strs of binary strings and two integers m and n (budgets of available 0s and 1s), return the size of the largest subset of strs such that the total count of 0s used is at most m and the total count of 1s used is at most n.
Input
An array strs of binary strings and integers m (zeros) and n (ones).
Output
An integer: the maximum number of strings selectable.
Constraints
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- 0 <= m, n <= 100
Examples
Example 1
Input
strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output
4
{"10","0001","1","0"} uses 5 zeros and 3 ones.
Example 2
Input
strs = ["10","0","1"], m = 1, n = 1
Output
2
Pick "0" and "1".