Length of the longest substring with the equal number of 1s and 0s.

PROBLEM STATEMENT

You are given a binary string 'S' of length 'N'. Your task is to find the length of the longest substring with an equal number of 1s and 0s.

Note:

1. The given string will only contain 0 and 1.

Input Format:

The first line contains an integer, ‘T,’ which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.

The first line of each test case contains one integer 'N', as described in the problem statement.

The second line of each test case contains one binary string of length 'N'.

Output Format:

For each test case, return an integer representing the length of the longest substring with the equal number of 1s and 0s.

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 <= 5 * 10^3

It is guaranteed that S will only contain '0' and '1'.

Time Limit: 1 second

Approach 1

In this brute force approach, we will check each substring one by one and check if the current substring has equal numbers of 0s and 1s. If it is true, then we will update our answer with the length of this substring if the length of the current substring is larger than our previous answer.

Steps:

Create a variable to store the answer (say, 'ANS') with 'ANS' = 0.
Run a loop from ‘i’ = 0 to ‘N’ and do:
- Run a loop from ‘j’ = ‘i’ to ‘N’ and do:
  - Create two variables 'COUNT0' and 'COUNT1', and initialize both of them to 0.
  - Run a loop from ‘k’ = ‘i’ to ‘j+1’ and do:
    - If S[k] == ‘0’, then increment 'COUNT0' by 1.
    - Else, increment 'COUNT1' by 1.
  - If 'COUNT0' == 'COUNT1', make 'ANS' = max('ANS', j - i + 1)
Finally, return the 'ANS' variable.

Try Problem

Approach 2

This approach is exactly the same as the previous approach, but here we will use a prefix sum array to check if the number of 0s and 1s are equal in a substring.
We can use the prefix sum array because if the summation of any substring is equal to half the length of the substring, then it means that there are equal numbers of 0s and 1s in the current substring.

Steps:

Create a variable to store the answer (say, 'ANS') with 'ANS' = 0.
Create a prefix sum array (say 'PREF') of size ‘N+1’.
Run a loop from ‘i’ = 0 to ‘N’ and do:
- 'PREF'[i+1] = 'PREF'[i] + (S[i] - ‘0’)
Run a loop from ‘i’ = 0 to ‘N’ and do:
- Run a loop from ‘j’ = ‘i’ to ‘N’ and do:
  - If 2*('PREF'[j + 1] - 'PREF'[i]) == (j - i + 1) , make 'ANS' = max('ANS', j - i + 1)
Finally, return the 'ANS' variable.

Try Problem

Approach 3

In this approach, we will consider 0 as -1. Therefore our task will be to find the longest substring having sum = 0 because if there are equal numbers of 1s and -1s in a substring, then the sum will be 0.
So, we will keep track of the current sum in the string, and we will use a hashmap to store the occurrence of a particular sum. If we find any sum again, then it means that the sum between the current point and the point where this sum appeared before will be zero and hence the number of 0s(currently considered as -1) and 1s are equal.
So, if we find such a sum, then we will update our answer if this length is greater than our previous answer.

Steps:

Create a variable to store the answer (say, 'ANS') with 'ANS' = 0 and a variable to store the sum (say 'SUM') with 'SUM' = 0.
Create a hashmap (say 'PRE_SUM') and initialize 'PRE_SUM'[0] = -1
Run a loop from i = 0 to ‘N’ and do:
- If S[i] == ‘0’, then 'SUM' -= 1
- else if S[i] == ‘1’ , then 'SUM' += 1
- If 'SUM' does not exists in 'PRE_SUM', then 'PRE_SUM'['SUM'] = i
- else make 'ANS' = max('ANS',i - 'PRE_SUM'['SUM'])
Finally, return the 'ANS' variable.