Find the longest substring in a binary string with an equal count of 0s and 1s

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²), 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: 

1. Let prefixSum[i] represent the sum of all the values until the ith index.
2. 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]
3. 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]
4. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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 -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String
   

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!