Split Binary String
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’.

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

Question

Split Binary String

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’.

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

Accepted Answer

Approach :

1) 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.

2) Now for each i from 0 to N - 1,
2.1) If str[i] is equal to ‘0’ , We increment ‘cnt0’ by 1.
2.2) If str[i] is equal to ‘1’ , We increment ‘cnt1’ by 1.

3) If ‘cnt0’ and ‘cnt1’ are equal, increment ‘cnt’ by 1.

4) If ‘cnt0’ is equal to ‘cnt1’ we return ‘cnt’.

5) Else, we return -1

TC : O(N), where N = length of the string
SC : O(1)

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n)Explanation:

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).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the length of str

*/



int splitString(string &str) 

{

    // To store the count of 0s and 1s

    int cnt0 = 0, cnt1 = 0;



    // To store the count of maximum substrings str can be divided into

    int cnt = 0;

    

    for (int i = 0; i < str.length(); i++) 

    {

        if (str[i] == '0') 

        {

            cnt0++;

        } 

        else 

        {

            cnt1++;

        }

        if (cnt0 == cnt1) 

        {

            cnt++;

        }

    }



    // It is not possible to split the string

    if (cnt0 != cnt1) 

    {

        return -1;

    }



    return cnt;

}

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where 'N' is the length of str
*/

public class Solution 
{
	public static int splitString(String str) 
	{
		// To store the count of 0s and 1s
		int cnt0 = 0, cnt1 = 0;

		// To store the count of maximum substrings str can be divided into
		int cnt = 0;

		for (int i = 0; i < str.length(); i++) 
		{
			if (str.charAt(i) == '0') 
			{
				cnt0++;
			} else 
			{
				cnt1++;
			}
			if (cnt0 == cnt1) 
			{
				cnt++;
			}
		}

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

		return cnt;
	}
}

Python (3.5)

'''

    Time complexity: O(N)
    Space complexity: O(1)
    
    Where 'N' is the length of str.

'''

def splitString(str):

    # To store the count of 0s and 1s
    cnt0 = 0
    cnt1 = 0

    # To store the count of maximum substrings str can be divided into
    cnt = 0
    for i in str:
        if i == '0':
            cnt0 += 1
        if i == '1':
            cnt1 += 1
        if cnt0 == cnt1:
            cnt += 1

    # It is not possible to split the string
    if cnt0 != cnt1:
        return -1

    return cnt

Top JPMorgan Chase & Co. Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in JPMorgan Chase & Co. Software Developer