# Split the binary string into substrings with equal number of 0s and 1s

Given a binary string **str** of length **N**, the task is to find the maximum count of consecutive substrings **str** can be divided into such that all the substrings are balanced i.e. they have equal number of **0s** and **1s**. If it is not possible to split **str** satisfying the conditions then print **-1**.**Example:**

Input:str = “0100110101”Output:4

The required substrings are “01”, “0011”, “01” and “01”.Input:str = “0111100010”Output:3Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

Input:str = “0000000000”

Output:-1

**Approach:** Initialize **count = 0** and traverse the string character by character and keep track of the number of **0s** and **1s** so far, whenever the count of **0s** and **1s** become equal increment the count. As in the given question, if it is not possible to split string then on that time count of 0s must not be equal to count of 1s** **then return **-1** else print the value of count after the traversal of the complete string.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return the count` `// of maximum substrings str` `// can be divided into` `int` `maxSubStr(string str, ` `int` `n)` `{` ` ` `// To store the count of 0s and 1s` ` ` `int` `count0 = 0, count1 = 0;` ` ` `// To store the count of maximum` ` ` `// substrings str can be divided into` ` ` `int` `cnt = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `if` `(str[i] == ` `'0'` `) {` ` ` `count0++;` ` ` `}` ` ` `else` `{` ` ` `count1++;` ` ` `}` ` ` `if` `(count0 == count1) {` ` ` `cnt++;` ` ` `}` ` ` `}` ` ` `// It is not possible to` ` ` `// split the string` ` ` `if` `(count0!=count1) {` ` ` `return` `-1;` ` ` `}` ` ` `return` `cnt;` `}` `// Driver code` `int` `main()` `{` ` ` `string str = ` `"0100110101"` `;` ` ` `int` `n = str.length();` ` ` `cout << maxSubStr(str, n);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the above approach` `class` `GFG` `{` `// Function to return the count` `// of maximum substrings str` `// can be divided into` `static` `int` `maxSubStr(String str, ` `int` `n)` `{` ` ` `// To store the count of 0s and 1s` ` ` `int` `count0 = ` `0` `, count1 = ` `0` `;` ` ` `// To store the count of maximum` ` ` `// substrings str can be divided into` ` ` `int` `cnt = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `{` ` ` `if` `(str.charAt(i) == ` `'0'` `)` ` ` `{` ` ` `count0++;` ` ` `}` ` ` `else` ` ` `{` ` ` `count1++;` ` ` `}` ` ` `if` `(count0 == count1)` ` ` `{` ` ` `cnt++;` ` ` `}` ` ` `}` ` ` `// It is not possible to` ` ` `// split the string` ` ` `if` `(count0 != count1)` ` ` `{` ` ` `return` `-` `1` `;` ` ` `}` ` ` `return` `cnt;` `}` `// Driver code` `public` `static` `void` `main(String []args)` `{` ` ` `String str = ` `"0100110101"` `;` ` ` `int` `n = str.length();` ` ` `System.out.println(maxSubStr(str, n));` `}` `}` `// This code is contributed by PrinciRaj1992` |

## Python3

`# Python3 implementation of the approach` `# Function to return the count` `# of maximum substrings str` `# can be divided into` `def` `maxSubStr(` `str` `, n):` ` ` ` ` `# To store the count of 0s and 1s` ` ` `count0 ` `=` `0` ` ` `count1 ` `=` `0` ` ` ` ` `# To store the count of maximum` ` ` `# substrings str can be divided into` ` ` `cnt ` `=` `0` ` ` ` ` `for` `i ` `in` `range` `(n):` ` ` `if` `str` `[i] ` `=` `=` `'0'` `:` ` ` `count0 ` `+` `=` `1` ` ` `else` `:` ` ` `count1 ` `+` `=` `1` ` ` ` ` `if` `count0 ` `=` `=` `count1:` ` ` `cnt ` `+` `=` `1` `# It is not possible to` ` ` `# split the string` ` ` `if` `count0 !` `=` `count1:` ` ` `return` `-` `1` ` ` ` ` `return` `cnt` `# Driver code` `str` `=` `"0100110101"` `n ` `=` `len` `(` `str` `)` `print` `(maxSubStr(` `str` `, n))` |

## C#

`// C# implementation of the above approach` `using` `System;` `class` `GFG` `{` `// Function to return the count` `// of maximum substrings str` `// can be divided into` `static` `int` `maxSubStr(String str, ` `int` `n)` `{` ` ` `// To store the count of 0s and 1s` ` ` `int` `count0 = 0, count1 = 0;` ` ` `// To store the count of maximum` ` ` `// substrings str can be divided into` ` ` `int` `cnt = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` `if` `(str[i] == ` `'0'` `)` ` ` `{` ` ` `count0++;` ` ` `}` ` ` `else` ` ` `{` ` ` `count1++;` ` ` `}` ` ` `if` `(count0 == count1)` ` ` `{` ` ` `cnt++;` ` ` `}` ` ` `}` ` ` `// It is not possible to` ` ` `// split the string` ` ` `if` `(count0 != count1)` ` ` `{` ` ` `return` `-1;` ` ` `}` ` ` `return` `cnt;` `}` `// Driver code` `public` `static` `void` `Main(String []args)` `{` ` ` `String str = ` `"0100110101"` `;` ` ` `int` `n = str.Length;` ` ` `Console.WriteLine(maxSubStr(str, n));` `}` `}` `// This code is contributed by PrinciRaj1992` |

## Javascript

`<script>` `// JavaScript implementation of the approach` `// Function to return the count` `// of maximum substrings str` `// can be divided into` `function` `maxSubStr(str, n)` `{` ` ` `// To store the count of 0s and 1s` ` ` `var` `count0 = 0, count1 = 0;` ` ` `// To store the count of maximum` ` ` `// substrings str can be divided into` ` ` `var` `cnt = 0;` ` ` `for` `(` `var` `i = 0; i < n; i++) {` ` ` `if` `(str[i] == ` `'0'` `) {` ` ` `count0++;` ` ` `}` ` ` `else` `{` ` ` `count1++;` ` ` `}` ` ` `if` `(count0 == count1) {` ` ` `cnt++;` ` ` `}` ` ` `}` ` ` `// It is not possible to` ` ` `// split the string` ` ` `if` `(count0 != count1) {` ` ` `return` `-1;` ` ` `}` ` ` `return` `cnt;` `}` `// Driver code` `var` `str = ` `"0100110101"` `;` `var` `n = str.length;` `document.write( maxSubStr(str, n));` `</script>` |

**Output:**

4

**Time complexity:** O(N) where N is the length of string **Space Complexity:** O(1)