Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 474 Ones and Zeroes - Problem Statement

LeetCode 474

Given an array of binary strings, and two integers mm (max zeros) and nn (max ones), return the maximum number of strings you can select such that total zeros m\leq m and total ones n\leq n.

For example, strings ["10","0001","111001","1","0"]["10", "0001", "111001", "1", "0"] with m=5,n=3m=5, n=3: select ["10","0001","1","0"]["10", "0001", "1", "0"] for 4 strings (4 zeros, 3 ones). Each string has a "cost" in two dimensions: zeros and ones. You want to find the largest count of strings while staying within both budgets. This is 0/1 knapsack with two capacities.