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.

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.

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. Empty Input Handling: How should the function behave if the input list strs is empty or if m and n are zero?
  2. Edge Case Verification: Are the values for m and n guaranteed to be non-negative?

Strategy

This problem can be approached using a dynamic programming (DP) solution, where we maintain a 2D DP array dp[i][j]. Here, dp[i][j] represents the maximum number of strings that we can pick with at most i 0s and j 1s.

Steps:

  1. Initial State:
    • Initialize a dp table with dimensions (m+1) x (n+1) to 0.
  2. DP Table Update:
    • For each string in strs, count the number of 0s and 1s.
    • Update the DP table from bottom-right to top-left, ensuring the current string’s zeros and ones contribute to the subset count accordingly.
  3. Result Extraction:
    • The result will be stored in dp[m][n].

Time Complexity

Thus, the overall time complexity is O(k * len + k * m * n), which simplifies to O(k * len + k * m * n).

Code

Here is the C++ implementation:

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (const string &s : strs) {
            int zeros = count(s.begin(), s.end(), '0');
            int ones = count(s.begin(), s.end(), '1');

            for (int i = m; i >= zeros; --i) {
                for (int j = n; j >= ones; --j) {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

Explanation:

  1. Initialization:
    • Initialize a 2D DP array where dp[i][j] represents the maximum number of strings we can pick with at most i zeros and j ones.
  2. Processing Each String:
    • For each string in the list, count its zeros (zeros) and ones (ones).
    • Update the DP table from the bottom-right to the top-left to prevent overwriting the values needed for current computation.
  3. Final Result:
    • The maximum subset size is stored in dp[m][n]. This is the answer to the problem.

By following this approach, we efficiently determine the largest subset of strings that meet the given constraints.

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