Strings: Divide binary string into sub strings with equal number of 0s and 1s.

Problem Statement:

You are given a string, you need to find the maximum count of substrings with equal number of 0s and 1s.

Example

Input: “0100110101”
Output: 4
The substrings are “01”, “0011”, “01” and “01”.

Solution

The solution is very simple.

We take a variable “count = 0” and traverse each character.

Then we keep track of the number of 0s and 1s, if the count is equal then increment the count.

The time complexity is O(N)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>

using namespace std;


int get_maximum_substring(string str, int n) 
{ 
  
    int count_0 = 0;
    int count_1 = 0; 
  
    int count = 0; 

    for (int i = 0; i < n; i++) 
    { 
        if (str[i] == '0') { 
            count_0++; 
        } 
        else { 
            count_1++; 
        } 
        if (count_0 == count_1) { 
            count++; 
        } 
    } 

    if (count_0 != count_1) { 
        return -1; 
    } 
  
    return count; 
} 
  
int main() 
{ 
    string str = "0100110101"; 
    int n = str.length(); 
  
    cout << get_maximum_substring(str, n); 
  
    return 0; 
}

Output:

4

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *