Split the Binary string into two substring with equal 0’s and 1’s

December 24, 2021

Split the binary substring into two substring

Today in this article we will learn how to Split the binary substring into two substring with equal 0 and 1.

Lets understand this with the help of an example:- 

  • Input: str = “0111100010” 
    Output: 3 
  • The required substring is “01”,”111000″,”10″ 
Split the binary substring into two substring

Algorithm

  • Take the binary string as input from the user.
  • Call the function maxSubStr() that will take the string and the size of string as parameter. 
  • Initialize count that will count the subsequence that matches the condition.
  • Traverse the entire string and take two count that is count of 0 and count of 1.
  • If the count of 1 and 0 is equal then increment the count .
  • If the count of 1 and 0 is not equal then return -1 .
  •  return the value of count that is the solution. 
Split the binary substring into two substring

C++ Code :-

#include <bits/stdc++.h>

using namespace std;

int maxSubStr(string str, int n) 
{

  // count0 and count1 store the count of 0s and 1s
  int count0 = 0, count1 = 0;

  //cnt to keep track of count of maximum substrings str can be divided into 
  int count = 0;

  for(int i = 0; i < n; i++) {
   if(str[i] == '0') {
    count0++;
  }
   else {
    count1++;
  }

  s+=str[i];

  if(count0 == count1) { 
    count++;
   }
 }

  //It is not possible to split the string
  if (count0!=count1) {
    return -1;
  }

  return count;
 }

  // Driver code
int main()
 {
   string str;
   cout<<"Enter the String : ";
   getline(cin,str);
   int n = str.length();

   cout<<"Number of Substring that have equal 0's and 1's = "<<maxSubStr(str, n);
   return 0;
 }

Output:-

Enter the String : 001101
Number of Substring that have equal 0's and 1's = 2
Enter the String : 01010011
Number of Substring that have equal 0's and 1's = 3