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