Approach
The naive approach is to count the number of 0s and 1s for every substring and check if they are the same in number. We can check this by using two nested loops, so the time complexity of this approach is O(N^{2}), where N = length of the string.
Efficient Solution
If we consider 0 as 1 in the given binary string, the problem gets reduced to finding the longest substring with a sum equal to 0.
Finding the longest subarray with a sum equal to 0:
We can find this using the prefix sum technique. If the same prefix sum occurs again in the array, the particular subarray in between will have a sum equal to 0.
Proof:
 Let prefixSum[i] represent the sum of all the values until the ith index.

Let there be two indexes i and j where j>i. Therefore:
prefixSum[i] = array[0] + array[1] + array[2] +â€¦ +array[i]
prefixSum[j] = array[0] + array[1] + array[2] â€¦+array[i]+.....+ array[j]

If (prefixSum[i]==prefixSum[j]), then
array[0] + array[1] + array[2] â€¦ + array[i] = array[0] + array[1] + array[2] â€¦ +array[i]+array[i+1].....+array[j]

Since i<j, from the above equation, we can easily say that:
array[i+1] + array[i+2] .. array[j] = 0.
Note: To keep track of the index for a particular prefix sum, we can use a hashmap.
Also check out  Substr C++
Code in C++
#include<iostream>
#include<unordered_map>
using namespace std;
string findLongestBalancedSubstring(string& s){
int sum = 0;
unordered_map<int,int> u_map;
u_map[0] = 1;
int maxLength = 0;
int startingIndex = 0;
int endingIndex = 0;
for(int i=0;i<s.size();i++){
// find the sum considering s[i] = 1 if s[i] = 0
if(s[i]=='0'){
sum;
}else{
sum++;
}
if(u_map.count(sum)==1){
/*
Therefore, we have a subarray with zero
sum from the index u_map[sum]+1 to the index i.
*/
int substringLength = i  u_map[sum];
if(maxLength<substringLength){
maxLength = substringLength;
endingIndex = i;
startingIndex = u_map[sum] + 1;
}
}else{
u_map[sum] = i;
}
}
if(maxLength==0){
return "1";
}else{
return s.substr(startingIndex,maxLength);
}
}
int main(){
string s1 = "10101010";
cout<<findLongestBalancedSubstring(s1)<<endl;
string s2 = "00100";
cout<<findLongestBalancedSubstring(s2)<<endl;
string s3 = "1101011010";
cout<<findLongestBalancedSubstring(s3)<<endl;
string s4 = "1111";
cout<<findLongestBalancedSubstring(s4)<<endl;
}
Output
10101010
01
01011010
1
Time Complexity
Since we are traversing the array just once, the time complexity is O(N), where N = length of the binary string.
Space Complexity
Since we can store the prefix sum for each index in the unordered map in the worst case, the space complexity is O(N), where N = length of the binary string.
Check out this problem  Subarray With 0 Sum
Frequently Asked Questions
1. What is the difference between a subsequence and a subarray (or substring in the case of a string)?
A subsequence is formed by deriving 0 or more elements from a sequence without changing the relative order of the elements in the original sequence. In comparison, a subarray is a contiguous part of a sequence. Therefore all the subarray will be subsequences too of a sequence, but vice versa is not true. For example: [1,2,4] is a subsequence for the sequence [1,2,3,4], but it is not the subarray.
2. How is an unordered_map implemented in C++?
Unordered_map is implemented using hash tables where keys are hashed into indices of a hash table so that the insertion is always randomized.
3. What is the difference between an unordered map and an ordered map?
A map (like a set) contains a sorted list of unique keys, whereas an unordered map contains a list of unique keys that may or may not be sorted. The time complexity of insertion in a map is O(log N), whereas, in unordered_map, it is O(1).
4. Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?
Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.
Key Takeaways
In this article, we learned to find the longest substring in a binary string with an equal count of 0s and 1s. Since questions related to strings are frequently asked in interviews, we recommend you practice more problems based on strings on Coding Ninjas Studio.
Recommended problems 
Are you planning to ace the interviews of reputed productbased companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!