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

Posted: 4 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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