MediumArrayStringDynamic Programming

Ones and Zeroes

1 approach, code in every language

You are given an array of binary strings and two integers m and n. Think of m as a budget of zeros and n as a budget of ones that you are allowed to spend.

You want to select a subset of the given strings such that the combined number of zeros across the chosen strings is at most m and the combined number of ones is at most n.

Return the size of the largest such subset that respects both budgets.

Example 1

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

Output: 4

The largest subset using at most 5 zeros and 3 ones is {"10","0001","1","0"}, which contains 4 strings.

Example 2

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

Output: 2

With one zero and one one available, the best choice is {"0","1"}, giving a subset of size 2.

Constraints

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

2D 0/1 Knapsack Over Zero and One Budgets

Treat each string as an item with a zero-cost and a one-cost, and run a 0/1 knapsack where dp[i][j] is the largest subset buildable using at most i zeros and j ones.

Loading animation…

Intuition

Each string is an item that costs a certain number of zeros and a certain number of ones, and picking it adds one to the subset size. This is a knapsack with two independent capacity dimensions instead of one. We keep a table dp[i][j] holding the maximum number of strings we can select while spending at most i zeros and j ones. For each string we update the table from high capacities down to low, which enforces that the string is used at most once. The final answer is dp[m][n].

Algorithm walkthrough

1Initialize a (m + 1) by (n + 1) grid dp filled with zeros; dp[i][j] means the best subset size within i zeros and j ones.
2For each string, count its zeros and ones.
3Iterate i from m down to that string's zero-count and j from n down to its one-count, updating dp[i][j] with the larger of itself and dp[i - zeros][j - ones] + 1.
4Sweeping both dimensions downward guarantees each string is added to any state at most once, preserving the 0/1 constraint.
5After all strings are processed, return dp[m][n], the largest subset fitting both budgets.

Implementation

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]

Time

O(L * m * n) where L is the number of strings; each string sweeps the full m-by-n capacity grid.

Space

O(m * n) for the two-dimensional DP table, reused across all strings.

Counting each string's zeros and ones adds O(total characters) which is dominated by the DP sweeps.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Stamping the Most Part Codes is our own problem on the technique behind Ones and Zeroes: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free