Given an array arr[] consisting of N binary strings, and two integers A and B, the task is to find the length of the longest subset consisting of at most A 0s and B 1s.
Examples:
Input: arr[] = {“1”, “0”, “0001”, “10”, “111001”}, A = 5, B = 3
Output: 4
Explanation:
One possible way is to select the subset {arr[0], arr[1], arr[2], arr[3]}.
Total number of 0s and 1s in all these strings are 5 and 3 respectively.
Also, 4 is the length of the longest subset possible.Input: arr[] = {“0”, “1”, “10”}, A = 1, B = 1
Output: 2
Explanation:
One possible way is to select the subset {arr[0], arr[1]}.
Total number of 0s and 1s in all these strings is 1 and 1 respectively.
Also, 2 is the length of the longest subset possible.
Naive Approach: Refer to the previous post of this article for the simplest approach to solve the problem.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Dynamic Programming Approach: Refer to the previous post of this article for the Dynamic Programming approach.
Time Complexity: O(N*A*B)
Auxiliary Space: O(N * A * B)
Space-Optimized Dynamic Programming Approach: The space complexity in the above approach can be optimized based on the following observations:
- Initialize a 2D array, dp[A][B], where dp[i][j] represents the length of the longest subset consisting of at most i number of 0s and j number of 1s.
- To optimize the auxiliary space from the 3D table to the 2D table, the idea is to traverse the inner loops in reverse order.
- This ensures that whenever a value in dp[][] is changed, it will not be needed anymore in the current iteration.
- Therefore, the recurrence relation looks like this:
dp[i][j] = max (dp[i][j], dp[i – zeros][j – ones] + 1)
where zeros is the count of 0s and ones is the count of 1s in the current iteration.
Follow the steps below to solve the problem:
- Initialize a 2D array, say dp[A][B] and initialize all its entries as 0.
- Traverse the given array arr[] and for each binary string perform the following steps:
- Store the count of 0s and 1s in the current string in variables zeros and ones respectively.
- Iterate in the range [A, zeros] using the variable i and simultaneously iterate in the range [B, ones] using the variable j and update the value of dp[i][j] to maximum of dp[i][j] and (dp[i – zeros][j – ones] + 1).
- After completing the above steps, print the value of dp[A][B] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subset of an array of strings// with at most A 0s and B 1sint MaxSubsetlength(vector<string> arr, int A, int B){ // Initialize a 2D array with its // entries as 0 int dp[A + 1][B + 1]; memset(dp, 0, sizeof(dp)); // Traverse the given array for (auto& str : arr) { // Store the count of 0s and 1s // in the current string int zeros = count(str.begin(), str.end(), '0'); int ones = count(str.begin(), str.end(), '1'); // Iterate in the range [A, zeros] for (int i = A; i >= zeros; i--) // Iterate in the range [B, ones] for (int j = B; j >= ones; j--) // Update the value of dp[i][j] dp[i][j] = max( dp[i][j], dp[i - zeros][j - ones] + 1); } // Print the result return dp[A][B];}// Driver Codeint main(){ vector<string> arr = { "1", "0", "0001", "10", "111001" }; int A = 5, B = 3; cout << MaxSubsetlength(arr, A, B); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to find the length of the// longest subset of an array of strings// with at most A 0s and B 1sstatic int MaxSubsetlength(String arr[], int A, int B){ // Initialize a 2D array with its // entries as 0 int dp[][] = new int[A + 1][B + 1]; // Traverse the given array for(String str : arr) { // Store the count of 0s and 1s // in the current string int zeros = 0, ones = 0; for(char ch : str.toCharArray()) { if (ch == '0') zeros++; else ones++; } // Iterate in the range [A, zeros] for(int i = A; i >= zeros; i--) // Iterate in the range [B, ones] for(int j = B; j >= ones; j--) // Update the value of dp[i][j] dp[i][j] = Math.max( dp[i][j], dp[i - zeros][j - ones] + 1); } // Print the result return dp[A][B];}// Driver Codepublic static void main(String[] args){ String arr[] = { "1", "0", "0001", "10", "111001" }; int A = 5, B = 3; System.out.println(MaxSubsetlength(arr, A, B));}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to find the length of the# longest subset of an array of strings# with at most A 0s and B 1sdef MaxSubsetlength(arr, A, B): # Initialize a 2D array with its # entries as 0 dp = [[0 for i in range(B + 1)] for i in range(A + 1)] # Traverse the given array for str in arr: # Store the count of 0s and 1s # in the current string zeros = str.count('0') ones = str.count('1') # Iterate in the range [A, zeros] for i in range(A, zeros - 1, -1): # Iterate in the range [B, ones] for j in range(B, ones - 1, -1): # Update the value of dp[i][j] dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1) # Print the result return dp[A][B]# Driver Codeif __name__ == '__main__': arr = [ "1", "0", "0001", "10", "111001" ] A, B = 5, 3 print (MaxSubsetlength(arr, A, B))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG { // Function to find the length of the // longest subset of an array of strings // with at most A 0s and B 1s static int MaxSubsetlength(string[] arr, int A, int B) { // Initialize a 2D array with its // entries as 0 int[, ] dp = new int[A + 1, B + 1]; // Traverse the given array foreach(string str in arr) { // Store the count of 0s and 1s // in the current string int zeros = 0, ones = 0; foreach(char ch in str.ToCharArray()) { if (ch == '0') zeros++; else ones++; } // Iterate in the range [A, zeros] for (int i = A; i >= zeros; i--) // Iterate in the range [B, ones] for (int j = B; j >= ones; j--) // Update the value of dp[i][j] dp[i, j] = Math.Max( dp[i, j], dp[i - zeros, j - ones] + 1); } // Print the result return dp[A, B]; } // Driver Code public static void Main(string[] args) { string[] arr = { "1", "0", "0001", "10", "111001" }; int A = 5, B = 3; Console.WriteLine(MaxSubsetlength(arr, A, B)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to find the length of the// longest subset of an array of strings// with at most A 0s and B 1sfunction MaxSubsetlength(arr, A, B){ // Initialize a 2D array with its // entries as 0 var dp = Array.from(Array(A + 1), ()=>Array(B + 1).fill(0)); // Traverse the given array arr.forEach(str => { // Store the count of 0s and 1s // in the current string var zeros = [...str].filter(x => x == '0').length; var ones = [...str].filter(x => x == '1').length; // Iterate in the range [A, zeros] for(var i = A; i >= zeros; i--) // Iterate in the range [B, ones] for(var j = B; j >= ones; j--) // Update the value of dp[i][j] dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1); }); // Print the result return dp[A][B];}// Driver Codevar arr = [ "1", "0", "0001", "10", "111001" ];var A = 5, B = 3;document.write(MaxSubsetlength(arr, A, B));// This code is contributed by noob2000</script> |
Output:
4
Time Complexity: O(N * A * B)
Auxiliary Space: O(A * B)
Efficient Approach : using array instead of 2d matrix to optimize space complexity
The optimization comes from the fact that the in this approach we use a 1D array, which requires less memory compared to a 2D array. However, in this approach code requires an additional condition to check if the number of zeros is less than or equal to the allowed limit.
Implementations Steps:
- Initialize an array dp of size B+1 with all entries as 0.
- Traverse through the given array of strings and for each string, count the number of 0’s and 1’s in it.
- For each string, iterate from B to the number of 1’s in the string and update the value of dp[j] as maximum of dp[j] and dp[j – ones] + (1 if (j >= ones && A >= zeros) else 0).
- Finally, return dp[B] as the length of the longest subset of strings with at most A 0’s and B 1’s.
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subset of an array of strings// with at most A 0s and B 1sint MaxSubsetlength(vector<string> arr, int A, int B){ // Initialize a 1D array with its // entries as 0 int dp[B + 1]; memset(dp, 0, sizeof(dp)); // Traverse the given array for (auto& str : arr) { // Store the count of 0s and 1s // in the current string int zeros = count(str.begin(), str.end(), '0'); int ones = count(str.begin(), str.end(), '1'); // Iterate in the range [B, ones] for (int j = B; j >= ones; j--) // Update the value of dp[j] dp[j] = max( dp[j], dp[j - ones] + ((j >= ones && A >= zeros) ? 1 : 0)); } // Print the result return dp[B];}// Driver Codeint main(){ vector<string> arr = { "1", "0", "0001", "10", "111001" }; int A = 5, B = 3; cout << MaxSubsetlength(arr, A, B); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;class Main { // Function to find the length of the // longest subset of an array of strings // with at most A 0s and B 1s static int MaxSubsetlength(List<String> arr, int A, int B) { // Initialize a 1D array with its // entries as 0 int[] dp = new int[B + 1]; Arrays.fill(dp, 0); // Traverse the given array for (String str : arr) { // Store the count of 0s and 1s // in the current string int zeros = 0, ones = 0; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '0') zeros++; else ones++; } // Iterate in the range [B, ones] for (int j = B; j >= ones; j--) { // Update the value of dp[j] dp[j] = Math.max(dp[j], dp[j - ones] + ((j >= ones && A >= zeros) ? 1 : 0)); } } // Print the result return dp[B]; } // Driver Code public static void main(String[] args) { List<String> arr = Arrays.asList("1", "0", "0001", "10", "111001"); int A = 5, B = 3; System.out.println(MaxSubsetlength(arr, A, B)); }} |
Python3
# Python program for above approach# Function to find the length of the# longest subset of an array of strings# with at most A 0s and B 1sdef MaxSubsetlength(arr, A, B): # Initialize a 1D array with its # entries as 0 dp = [0] * (B + 1) # Traverse the given array for str in arr: # Store the count of 0s and 1s # in the current string zeros = str.count('0') ones = str.count('1') # Iterate in the range [B, ones] for j in range(B, ones - 1, -1): # Update the value of dp[j] dp[j] = max( dp[j], dp[j - ones] + ((j >= ones and A >= zeros) == True)) # Print the result return dp[B]# Driver Codearr = ["1", "0", "0001", "10", "111001"]A, B = 5, 3print(MaxSubsetlength(arr, A, B)) |
C#
// importing necessary namespacesusing System;using System.Collections.Generic;// defining main classclass MainClass{ // Function to find the length of the longest subset // of an array of strings with at most A 0s and B 1s static int MaxSubsetlength(List<string> arr, int A, int B) { // Initialize a 1D array with its entries as 0 int[] dp = new int[B + 1]; Array.Fill(dp, 0); // Traverse the given array foreach (string str in arr) { // Store the count of 0s and 1s in the current string int zeros = 0, ones = 0; foreach (char c in str) { if (c == '0') zeros++; else ones++; } // Iterate in the range [B, ones] for (int j = B; j >= ones; j--) { // Update the value of dp[j] dp[j] = Math.Max(dp[j], dp[j - ones] + ((j >= ones && A >= zeros) ? 1 : 0)); } } // Return the result return dp[B]; } // Driver Code public static void Main(string[] args) { // Define the input List<string> arr = new List<string> {"1", "0", "0001", "10", "111001"}; int A = 5, B = 3; // Call the function and print the result Console.WriteLine(MaxSubsetlength(arr, A, B)); }} |
Javascript
// Function to find the length of the// longest subset of an array of strings// with at most A 0s and B 1sfunction MaxSubsetlength(arr, A, B) { // Initialize a 1D array with its // entries as 0 let dp = new Array(B + 1).fill(0); // Traverse the given array for (let i = 0; i < arr.length; i++) { const str = arr[i]; // Store the count of 0s and 1s // in the current string let zeros = 0, ones = 0; for (let j = 0; j < str.length; j++) { if (str.charAt(j) === '0') zeros++; else ones++; } // Iterate in the range [B, ones] for (let j = B; j >= ones; j--) { // Update the value of dp[j] dp[j] = Math.max(dp[j], dp[j - ones] + ((j >= ones && A >= zeros) ? 1 : 0)); } } // Print the result return dp[B];}// Driver Codeconst arr = ["1", "0", "0001", "10", "111001"];const A = 5, B = 3;console.log(MaxSubsetlength(arr, A, B)); |
Output :
4
Time Complexity: O(N * A * B)
Auxiliary Space: O(B)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
