Problem 30.8 · Knapsack DPMedium

Ones and Zeroes

What it teaches: A knapsack with two capacities at once.

Practise it on judges as “Ones and Zeroes”.

The problem

Return the size of the largest subset of binary strings with at most m zeros and n ones in total.

Example 1

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

Constraints

1 ≤ strs ≤ 600
1 ≤ m, n ≤ 100

Pattern clues in the wording

→ Two resource limits
→ Each item used once

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	strs = ["10","0001","111001","1","0"] m = 5 n = 3	4
2	strs = ["10","0","1"] m = 1 n = 1	2

From slow to fast

Approaches

1. 2D 0/1 knapsack · O(len × m × n)

2D 0/1 knapsack

Time O(len × m × n) Space O(m × n)

Count each string's zeros and ones; for z from m down, o from n down: dp[z][o] = max(dp[z][o], dp[z − zeros][o − ones] + 1).

Approach 1

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 z = m; z >= zeros; z--)
                for (int o = n; o >= ones; o--)
                    dp[z][o] = Math.max(dp[z][o], dp[z - zeros][o - ones] + 1);
        }
        return dp[m][n];
    }
}

Verdict: Same idea, one more dimension.

Before you submit

Edge cases and common mistakes

Test these inputs

A string that alone exceeds a limit
m or n = 0

Mistakes people make

Greedy by shortest strings.

Interview

Follow-up questions

How does the state grow with k resources?

Command Palette

The problem

Approaches

2D 0/1 knapsack

Edge cases and common mistakes

Follow-up questions