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

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
Media.netMcKinsey & CompanyFlipkart limited

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5
01100
Sample Output 1:
4
Explanation for sample input 1:
The output is 4 because the substring from index 1 to 4(we are considering 0-based indexing) contains equal numbers of 0s and 1s and its length is 4.
Sample Input 2:
1
6
111111
Sample Output 2:
0
Explanation for sample input 2:
Since we can not find any substring having equal numbers of 0s and 1s, therefore the answer is 0.
Hint

Try to iterate on each substring one by one.

Approaches (3)
Brute Force Approach

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.
Time Complexity

O(N^3), where ‘N’ is the length of the given string.

 

We are iterating on each substring of the given string. Since the number of substrings in a string is in the order of N^2 and finally we iterate on the selected substring, therefore the time complexity is in the order of O(N^3).

Space Complexity

O(1). 

 

Since constant extra space is required.

Code Solution
(100% EXP penalty)
Length of the longest substring with the equal number of 1s and 0s.
Full screen
Console