Split Binary String

Easy
0/40
Average time to solve is 15m
5 upvotes
Asked in company
Amazon

Problem statement

Chintu has a long binary string ‘str’. A binary string is a string that contains only 0 and 1. He considers a string ‘beautiful’ if and only if the number of 0's and 1's in the string are equal.

For example :

0011 , 1100 , 101010 etc are beautiful strings whereas 1110, 0001,10101 etc are not beautiful strings.

Now Chintu wants to split the string into substrings such that each substring is beautiful. Can you help Chintu to find the maximum number of beautiful strings he can split the string into? If it is not possible to split the string in such a way that all strings are beautiful, return -1.

For example :

Let the given string be “101001”
We will return 3 as we can divide the string into 3 beautiful strings “10” “10” and “01’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains the string ‘str’.
Output Format : 
For each test case, return the maximum number of substrings, ‘str’ can be split into such that each substring is beautiful.

If there are none, return -1.

Output for each test case will be printed in a new line.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100
1 <= N <= 5000

Time limit: 1 second
Sample Input 1 :
2
10101100
11111111
Sample Output 1 :
3
-1
Explanation of sample input 1 :
In the first test case,
We can split the given string into 3 beautiful substrings ‘10’, ‘10’, and ‘1100’. Hence we return 3.

In the second test case,
We cannot split the given string into any beautiful string hence we return -1.
Sample Input 2 :
2
1110001100
0000111
Sample Output 2 :
2
-1
Hint

Iterate through the given string and check the beautiful condition.

Approaches (1)
Iterative approach

The key idea in solving this problem is to simply iterate through the given string and keep the count of 1s and 0s in the string. Whenever we have the count of 1 and 0 to be equal, we increment the count of beautiful strings by 1. If we find no beautiful string, we simply return -1.

 

The algorithm will be -

 

  • Take two variables ‘cnt0’ and ‘cnt1’ to store the count of 0s and 1s respectively. Also, take a variable ‘cnt’ which stores the count of the number of substrings.
  • Now for each i from 0 to N - 1,
    • If str[i] is equal to ‘0’
      • We increment ‘cnt0’ by 1.
    • If str[i] is equal to ‘1’
      • We increment ‘cnt1’ by 1.
    • If ‘cnt0’ and ‘cnt1’ are equal, increment ‘cnt’ by 1.
  • If ‘cnt0’ is equal to ‘cnt1’ we return ‘cnt’.
  • Else, we return -1
Time Complexity

O(N), where ‘N’ is the length of the string

 

As each index of the string will be visited at most once the time complexity will be O(N). 

Space Complexity

O(1)

 

Since we are using constant space, therefore the space complexity is O(1).

Code Solution
(100% EXP penalty)
Split Binary String
Full screen
Console