algoadvance

Leetcode 474. Ones and Zeroes

Problem Statement

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 0s and n 1s in the subset.
• A subset is a combination of elements obtained by deleting some (possibly none) of the array elements.

Example 1:

• Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
• Output: 4
• Explanation: The largest subset with at most 5 zeroes and 3 ones is {"10", "0001", "1", "0"}, thus the answer is 4.

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.

Clarifying Questions

1. What are the constraints for m and n?
   • 1 <= strs.length <= 600
   • 1 <= strs[i].length <= 100
   • strs[i] consists only of ‘0’ and ‘1’.
   • 1 <= m, n <= 100
2. Should the subset maintain order?
   • No, the subset does not need to maintain order.
3. Are empty subsets allowed?
   • While valid, they would not contribute to maximizing the size of the subset, so they are not practically useful for solving the problem.

Strategy

We can solve this problem using Dynamic Programming. The idea is to create a DP array dp[i][j] which represents the maximum size of the subset that can be formed with at most i zeros and j ones.

1. Initialization:
   • Initialize a DP array dp of size (m+1) x (n+1) with all zeros as initially, with zero 0s and 1s, no subset can be formed other than the empty one.
2. Iterating through strs:
   • For each string in strs, count the number of 0s and 1s.
   • Update the DP array from the bottom-right corner to top-left corner to avoid re-using the same string in multiple counts unintentionally.
3. DP Transition:
   • If a string has zeros number of 0s and ones number of 1s, for each dp[i][j] from m to zeros and n to ones, we check:

     dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])
     

4. Result:
   • The value dp[m][n] will contain the maximum size of the subset we seek.

Time Complexity

The time complexity is (O(len \cdot m \cdot n)) where len is the length of strs. This is because we iterate through all strings and for each string, we update the m x n DP array.

Code

public class Solution {

    public int findMaxForm(String[] strs, int m, int n) {

        int[][] dp = new int[m + 1][n + 1];

        for (String str : strs) {
            int zeros = 0, ones = 0;

            // Count the number of 0s and 1s in the current string
            for (char c : str.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }

            // Update the dp array from bottom to top to prevent reuse
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5;
        int n = 3;
        System.out.println(solution.findMaxForm(strs, m, n)); // Output: 4
    }
}

This code initializes the DP array, processes each string to update the DP values, and finally returns the maximum subset size that meets the criteria.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?