LeetCode 474.

Question

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

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example

Example 1:

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

Output: 4

Explanation: The largest subset with at most 5 0’s and 3 1’s is {“10”, “0001”, “1”, “0”}, so the answer is 4. Other valid but smaller subsets include {“0001”, “1”} and {“10”, “1”, “0”}. {“111001”} is an invalid subset because it contains 4 1’s, greater than the maximum of 3.
Example 2:

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

Output: 2

Explanation: The largest subset is {“0”, “1”}, so the answer is 2.

Complexity

Time complexity: O(mnlen(strs))
Space complexity: O(mnlen(strs))

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int oneCount = 0;
        int zeroCount = 0;
        for(int i = 1; i < strs.length + 1; ++i) {
            String str = strs[i - 1];
            int[] count = count(str);
            zeroCount += count[0];
            oneCount += count[1];
            for(int j = 0; j < m + 1; ++j) {
                for(int k = 0; k < n + 1; ++k) {
                    if (j == 0 && k == 0) {
                        dp[i][j][k] = 0;
                    }
                    else if (zeroCount <= j && oneCount <= k) {
                        dp[i][j][k] = i;
                    }
                    else if (j >= count[0] && k >= count[1]){
                        dp[i][j][k] = 
                            Math.max(dp[i - 1][j][k], dp[i - 1][j - count[0]][k - count[1]] + 1);
                    }
                    else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                } 
            }   
        }
        
        return dp[strs.length][m][n];
    }
    
    public int[] count(String str) {
        int[] res = new int[2];
        for (char c : str.toCharArray()) {
            if (c == '0') res[0]++;
            else res[1]++;
        }
        
        return res;
    }
}

Check out the description of this problem at LC 474.