1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Efficient Solution
4.
Code in C++
4.1.
Time Complexity
4.2.
Space Complexity
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

Gaurish Anand
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

Finding substrings and subsequences that satisfy particular constraints is commonly asked in Amazon, Microsoft, and Adobe. In this article, we will discuss one of those problems.

Before beginning with this question, letâ€™s recap what a substring of a string is. A substring is a contiguous part of a string placed between two specified indices. For example, non-empty substrings of the string â€śabcâ€ť are â€śaâ€ť, â€śbâ€ť, â€ścâ€ť, â€ťabâ€ť, â€śbcâ€ť, and â€śabcâ€ť.

Also See, kth largest element in an array, and Euclid GCD Algorithm

## Problem Statement

Given a binary string, find the longest substring with an equal count of 0s and 1s. If no such substrings exist, return â€ś-1â€ť. Example:

Input: â€ś1101011010â€ť
Output: 01011010
Explanation: Since in the string â€ś01011010â€ť, 0s and 1s count is 4. Therefore it is the longest substring in the above string, with an equal number of 0s and 1s.

Input: â€ś1111â€ť
Output: -1
Explanation: Since in the above string, we donâ€™t have any 0. Therefore no substring with an equal count of 0s and 1s exists in the above string.

Input: â€ś00100â€ť
Output: 01

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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(N2), 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;
}``````

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

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 product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Live masterclass