Given a binary string S of size N, the task is to find the maximum number of partitions of string S such that the ratio of the number of 0 and 1 in all the partitions are the same.
Examples:
Input: S = “010100001”
Output: 3
Explanation:
The substring [0, 2], [3, 5] and [6, 8] have the same ratio of ‘0′ and ‘1’ is 2:1. Therefore, the maximum possible partition is 3.Input: str=”001101″
Output: 2
Naive Approach: The naive approach is to generate all the partitions of string S and find the partition that has a maximum frequency of 0 to 1 ratio.
Time Complexity: O(N*2N)
Auxiliary Space: O(N)
Efficient Approach: To solve this problem first see some observations:
Let say there are two prefix strings that obtain the same ratio of 0 and 1. Then it is possible to divide the larger prefix into two with the same ratio. For eg- S = “0101” the prefix [0, 1] has the ratio of 1:1 and the prefix[0, 3] has the ratio of 1:1 then it is possible to partition the string in two with the ratio 1:1. Therefore, just count the number of prefixes that has the same 0 and 1 ratio as that of string S and print the number of prefix with that ratio.
Follow the steps below to solve the problem:
- Initialize two integer variables, say count_of_0 and count_of_1 as 0 to store the count of the number of ‘0’ and ‘1’ characters respectively.
- Initialize a hash map, say M which stores the frequency of ratio of ‘0′ to ‘1′.
- Iterate in the range [0, N-1] using the variable i and perform the following steps:
- If S[i] is equal to ‘0’ then increment the count_of_0 by 1, Otherwise increment count_of_1 by 1.
- Find the GCD of count_of_0 and count_of_1 and store it in a variable, say GCD.
- If GCD = 0, then increment m[{count_of_0, count_of_1}] by 1.
- If GCD != 0, then increment the value of m[{count_of_0 / GCD, count_of_1 / GCD}] by 1.
- Print the value of m[{count_of_0 / GCD, count_of_1 / GCD}] as the answer.
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 maximum partition such// that the ratio of 0 and 1 are samevoid maximumPartition(string S){ // Size of string int N = S.size(); // Variable to store the frequency // of 0 and 1 int count_of_0 = 0, count_of_1 = 0; // Map to store frequency of ratio map<pair<int, int>, int> m; int ans; // Traverse the string for (int i = 0; i < N; i++) { // Increment the frequency // of 0 by 1 if s[i] = 0 if (S[i] == '0') count_of_0++; // Otherwise increment frequency of 1 else count_of_1++; int first = count_of_0, second = count_of_1; // Find GCD of count_of_0 and count_of_1 int GCD = __gcd(count_of_0, count_of_1); // Convert the count of 0 and count of 1 // in the coprime numbers if (GCD != 0) { first = count_of_0 / GCD; second = count_of_1 / GCD; } // Increase the ratio of 0 and 1 by 1 m[{ first, second }]++; ans = m[{ first, second }]; } cout << ans << endl;}// Driver Codeint main(){ // Given Input string S = "001101"; // Function Call maximumPartition(S); return 0;} |
Java
import java.util.HashMap;public class MaximumPartition { // Function to find the gcd of two numbers static int gcd(int a, int b) { int result = Math.min(a, b); // Find the minimum of a and b while (result > 0) { if (a % result == 0 && b % result == 0) { break; } result--; } // return the gcd of a and b return result; } // Function to find maximum partition such that the // ratio of 0 and 1 are same static void maximumPartition(String S) { // Size of string int N = S.length(); // Variables to store the frequency of 0 and 1 int countOf0 = 0; int countOf1 = 0; // Map to store the frequency of ratio HashMap<String, Integer> m = new HashMap<>(); int ans = 0; // Traverse the string for (int i = 0; i < N; i++) { // Increment the frequency of 0 by 1 if S[i] = 0 if (S.charAt(i) == '0') { countOf0++; } else { // Otherwise, increment the frequency of 1 countOf1++; } int first = countOf0; int second = countOf1; // Find the gcd of countOf0 and countOf1 int GCD = gcd(countOf0, countOf1); // Convert the count of 0 and count of 1 into // coprime numbers if (GCD != 0) { first = countOf0 / GCD; second = countOf1 / GCD; } // Increase the ratio of 0 and 1 by 1 String w = first + "" + second; if (!m.containsKey(w)) { m.put(w, 0); } m.put(w, m.get(w) + 1); ans = m.get(w); } System.out.println(ans); } public static void main(String[] args) { // Given Input String S = "001101"; // Function Call maximumPartition(S); }} |
Python3
# Python program for the above approach# Function to find maximum partition such# that the ratio of 0 and 1 are same# JavaScript code for the above approachimport mathdef __gcd(a, b) : result = min(a, b) #// Find Minimum of a nd b while (result > 0) : if a % result == 0 and b % result == 0 : break result-=1 return result #// return gcd of a nd b # Function to find maximum partition such#that the ratio of 0 and 1 are samedef maximumPartition(S) : #// Size of string N = len(S) #// Variable to store the frequency #// of 0 and 1 count_of_0 = 0 count_of_1 = 0 #// Map to store frequency of ratio m = {} ans = 0 # Traverse the string for i in range (N) : # Increment the frequency # of 0 by 1 if s[i] = 0 if S[i] == '0': count_of_0+=1; # Otherwise increment frequency of 1 else: count_of_1+=1; first = count_of_0 second = count_of_1 # // Find GCD of count_of_0 and count_of_1 GCD = __gcd(count_of_0, count_of_1); #// Convert the count of 0 and count of 1 # // in the coprime numbers if GCD != 0 : first = math.floor(count_of_0 / GCD); second = math.floor(count_of_1 / GCD); #// Increase the ratio of 0 and 1 by 1 w = str(first) + str(second) if str(first) + str(second) not in m: m[w] = 0 m[w] += 1 ans = m[w] print(ans); # Driver Code # Given InputS = "001101"; # Function CallmaximumPartition(S);# This code is contributed by poojaagarwal2. |
C#
using System;using System.Collections.Generic;public class MaximumPartition{ // Function to find the gcd of two numbers static int gcd(int a, int b) { int result = Math.Min(a, b); // Find the minimum of a and b while (result > 0) { if (a % result == 0 && b % result == 0) { break; } result--; } // return the gcd of a and b return result; } // Function to find maximum partition such that the // ratio of 0 and 1 are same static void maximumPartition(string S) { // Size of string int N = S.Length; // Variables to store the frequency of 0 and 1 int countOf0 = 0; int countOf1 = 0; // Map to store the frequency of ratio Dictionary<string, int> m = new Dictionary<string, int>(); int ans = 0; // Traverse the string for (int i = 0; i < N; i++) { // Increment the frequency of 0 by 1 if S[i] = 0 if (S[i] == '0') { countOf0++; } else { // Otherwise, increment the frequency of 1 countOf1++; } int first = countOf0; int second = countOf1; // Find the gcd of countOf0 and countOf1 int GCD = gcd(countOf0, countOf1); // Convert the count of 0 and count of 1 into // coprime numbers if (GCD != 0) { first = countOf0 / GCD; second = countOf1 / GCD; } // Increase the ratio of 0 and 1 by 1 string w = first.ToString() + second.ToString(); if (!m.ContainsKey(w)) { m.Add(w, 0); } m[w] += 1; ans = m[w]; } Console.WriteLine(ans); } public static void Main(string[] args) { // Given Input string S = "001101"; // Function Call maximumPartition(S); }} |
Javascript
// JavaScript code for the above approach function __gcd(a, b) { let result = Math.min(a, b); // Find Minimum of a nd b while (result > 0) { if (a % result == 0 && b % result == 0) { break; } result--; } return result; // return gcd of a nd b } // Function to find maximum partition such // that the ratio of 0 and 1 are same function maximumPartition(S) { // Size of string let N = S.length; // Variable to store the frequency // of 0 and 1 let count_of_0 = 0, count_of_1 = 0; // Map to store frequency of ratio let m = new Map(); let ans = 0; // Traverse the string for (let i = 0; i < N; i++) { // Increment the frequency // of 0 by 1 if s[i] = 0 if (S[i] == '0') count_of_0++; // Otherwise increment frequency of 1 else count_of_1++; let first = count_of_0, second = count_of_1; // Find GCD of count_of_0 and count_of_1 let GCD = __gcd(count_of_0, count_of_1); // Convert the count of 0 and count of 1 // in the coprime numbers if (GCD != 0) { first = Math.floor(count_of_0 / GCD); second = Math.floor(count_of_1 / GCD); } // Increase the ratio of 0 and 1 by 1 if (!m.has(first.toString() + second.toString())) { m.set(first.toString() + second.toString(), 1); } else { m.set(first.toString() + second.toString(), m.get(first.toString() + second.toString()) + 1) } ans = m.get(first.toString() + second.toString()) } console.log(ans); } // Driver Code // Given Input let S = "001101"; // Function Call maximumPartition(S);// This code is contributed by Pooja Agrawal |
Output
2
Time complexity: O(N log N)
Auxiliary Space: O(N)
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!
