Leetcode 474. Ones and Zeroes

Clarification

Okay, so first I’ll restate the problem to make sure I understand it correctly.

We are given an array of binary strings strs, and two integers m and n.

• m is the maximum number of 0s we can use.
• n is the maximum number of 1s we can use.
• Each string can be selected at most once.
• We want to return the maximum number of strings we can select without exceeding either limit.

Each string can only be used once, right?
And m and n are separate constraints — I cannot use more than m zeroes or more than n ones?
We only need the maximum number of strings, not the actual strings?

Assuming yes, this is starting to look like a 0/1 knapsack problem with two capacities.

Brute-force Approach

The simplest approach would be to consider every possible subset of strings.

For every string, I basically have two choices:

• take it
• don't take it

So with k strings, there are 2^k possible subsets. For each subset, I could count how many zeroes and ones it uses and check whether it's valid. That works conceptually, but the exponential time complexity is too expensive.

Optimization

This is essentially 0/1 knapsack, except instead of having one capacity like weight, I have two capacities:

• number of zeroes
• number of ones

For each string, its "weight" is (zeroCount, oneCount), and its profit is 1, because selecting any string increases the number of selected strings by one.

So I can define: dp[i][j][k] as the maximum number of strings I can select using at most j zeroes and k ones in the subarray of strs starting from i.

Then for every string, suppose it contains:

• zeros = z
• ones = o

I have two choices.

• Don't take it: dp[i + 1][j][k]
• Or take it: dp[i + 1][j - z][k - o] + 1

So the transition is:

dp[i][j][k] =
max(
    dp[i + 1][j][k],
    dp[i + 1][j - z][k - o] + 1
)

If there are k strings, and the two capacities are m and n:

• Time: O(k * m * n)
• Space: O(k * m * n)

I also need to count the zeroes and ones in each string, but that's proportional to the total number of characters, so it doesn't change the main DP complexity.

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 0-1 knapsack

        // maximum amount of strings can be put into the knapsack with constraints m, n, within the range [i...)
        Integer[][][] memo = new Integer[strs.length + 1][m + 1][n + 1];

        int[] zeros = new int[strs.length];
        int[] ones = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            int one = 0, zero = 0;
            for (int c = 0; c < s.length(); c++) {
                if (s.charAt(c) == '1') {
                    one++;
                }
                else {
                    zero++;
                }
            }
            zeros[i] = zero;
            ones[i] = one;
        }

        return dp(strs, m, n, 0, memo, zeros, ones);
    }

    private int dp(String[] strs, int m, int n, int available, Integer[][][] memo, int[] zeros, int[] ones) {
        if (available == strs.length) {
            return 0;
        }
        if (m < 0 || n < 0) {
            return 0;
        }
        if (memo[available][m][n] != null) {
            return memo[available][m][n];
        }

        int result = 0;
        int zero = zeros[available], one = ones[available];
        if (zero <= m && one <= n) {
            result = Math.max(
                    dp(strs, m - zero, n - one, available + 1, memo, zeros, ones) + 1,
                    dp(strs, m, n, available + 1, memo, zeros, ones)
            );
        }
        else {
            result = dp(strs, m, n, available + 1, memo, zeros, ones);
        }
        memo[available][m][n] = result;

        return result;
    }
}

Follow-up