474. Ones and Zeroes: Leetcode Step-by-Step Approach

Ones and Zeroes - LeetCode

Photo by Johen Redman on Unsplash

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 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.

APPROACH:

1. 3D Array
— The class contains a 3D array `dp` to store the results of subproblems.
— There’s a `recur` method that performs the recursive dynamic programming approach to solve the problem.

2. ‘recur’ Method:
— The `recur` method is a recursive function that calculates the maximum size of the subset based on the conditions mentioned.
— It uses memoization by checking if the result for the current parameters (`m`, `n`, `i`) is already computed (`dp[m][n][i] != -1`).
— It counts the number of zeros and ones in the current string and checks if including the string in the subset is feasible based on the remaining `m` and `n`.
— If feasible, it calculates the maximum size by either including or excluding the current string.

3. ‘findMaxForm’ Method:
— It initializes the `dp` array with -1, indicating that no subproblems are solved yet.
— It calls the `recur` method with the initial parameters.

4. ‘main’ Function:
— It creates an instance of the `Solution` class.
— Defines a vector of binary strings (`strs`) and sets values for `m` and `n`.
— Calls the `findMaxForm` method to get the result and prints it.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

class Solution {
public:
    
    int dp[101][101][601];
    
    int recur(vector<string>& strs, int m, int n, int i ){
        
        if(i >= strs.size() || n<0 || m<0 ){
            return 0;
        }
        if(dp[m][n][i] != -1)
            return dp[m][n][i];
        
      int zeros = count(strs[i].begin(),strs[i].end(),'0');
      int ones = count(strs[i].begin(),strs[i].end(),'1');
        
        if(m-zeros>=0 && n-ones>=0) 
        {
          return  dp[m][n][i] = max(1+recur(strs,m-zeros,n-ones,i+1),recur(strs,m,n,i+1));
        }
        else
        {
          return dp[m][n][i] =recur(strs,m,n,i+1); 
        }
         
    }
    
    int findMaxForm(vector<string>& strs, int m, int n) {
         
        memset(dp,-1,sizeof(dp));
       
        
        return recur(strs,m,n,0);
        
    }
};

int main() {
    Solution solution;
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5;
    int n = 3;

    int maxForm = solution.findMaxForm(strs, m, n);

    cout << "Maximum number of forms that can be selected is: " << maxForm << endl;

    return 0;
}