Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Efficient Solution
4.
Code in C++
4.1.
Time Complexity 
4.2.
Space Complexity 
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author 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

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

Previous article
Count of All Substrings in a Binary String in Which Count of 1’s is Strictly More than the Count of 0’s
Next article
Check if Count of 1s can be Made Greater in a Binary string by Changing 0s Adjacent to 1s
Live masterclass