Longest substring with equal number of 0s and 1s

Given a string consisting of only 0s and 1s, How do we write a program to find the longest sub string with equal number of 0s and 1s in it?

For example consider the string “01001”, the longest string with equal number of 0s and 1s is “1001”.

Let us look at the solution approaches.
Considering 0 as -1 and 1 as +1, at each index we maintain a cumulative “balance” value.

Here balance is the difference between the count of 1 and 0 appeared so far.

For example for the example string “01001”, the balance values are as follows

Index:     0   1   2   3   4
Bit:       0   1   0   0   1
Balance: -1   0 -1 -2 -1

In this balance array, the longest distance between any two equal values gives us the required result.

In the above example, balance value “-1” appear at index 0 and index 4. So 4-0 = 4 is the maximum length of the sub string with equal number of 0,1s.
and the sub string is 1001 ( sub string between 1 and 4 indices).

Let us look at two possible approaches which utilizes the above property.

Method 1: Simple O(n²) approach

This method iterates through all possible sub strings and finds out which one is the longest with equal number of 0, 1s.
To check if a sub string has equal number of 0,1, we check the balance value at each index. If it is zero, we will update the maximum length if required.

Method 2: Efficient O(n) approach

This method needs extra space to run in O(n) time. For a string of length n, the range of balance values are in the range (-n, n); -n when all entries are 0, and n when all entries are 1.

We will create an array of size 2n+1 which acts as a hash table for all possible balance values. This table stores the leftmost index in the array for each balance value.

Since the array is 0 indexed, table[n+b] stores the leftmost index with balance b. At each index we keep on updating the balance value.

If there is no entry in the table with the given balance, we store the index for b.
If the table contains a previous entry with the same balance value, we check if the sub string between this previous index and the current index is the longest sub string.

Below is the C++ program to which implements the two approaches discussed above.

	// LongestSubstringEqual01.cpp : Given a string consisting of 0 and 1s.
	//Find the longest substring with equal number of zeros and ones

	#include <iostream>
	#include <string>
	#include <vector>
	#include <hash_map>

	using namespace std;

	//Simple O(n^2) implementation
	string longestBalancedSubstr1(string input)
	{
	int len = input.size();
	int i,j;
	int balance = 0;
	int maxLen = 0;
	int mStart = -1;

	// search through all possible substrings
	for( i = 0; i < len-1; i++ )
	{
	balance = (input[i] == '0')? -1 : 1;

	for( j = i+1; j < len ; j++ )
	{
	balance += (input[j] == '0')? -1 : 1;

	if( balance == 0 )
	{
	if( maxLen < j-i+1 )
	{
	maxLen = j-i+1;
	mStart = i;
	}
	}
	}
	}
	if( maxLen > 0 )
	return input.substr(mStart, maxLen);
	return "";
	}

	//Efficient O(n) implementation with O(n) extra space
	string longestBalancedSubstr(string input)
	{
	int len = input.size();
	//stores the left most index for a particular balance value
	vector<int> balanceMap( 2 * len + 1, -1);

	int i;
	int balance = 0;
	int maxLen = 0;
	int maxStart = -1;

	for( i = 0; i < len; i++ )
	{
	balance += (input[i] == '0') ? -1: 1;

	if( balance == 0 ) //substr(0,i) has equal number of 0,1s
	{
	if( i+1 > maxLen ) //check if it is the longest substring
	{
	maxLen = i+1;
	maxStart = 0;
	}
	}
	else
	{
	int prevIndex = balanceMap[ len + balance ];
	if( prevIndex == -1 )
	{
	balanceMap[ len+balance ] = i;
	}
	else //substr( prevIndex+1, i) has equal number of 0,1s
	{
	if( (i-prevIndex) > maxLen ) //check if it is the longest substring
	{
	maxLen = i-prevIndex;
	maxStart = prevIndex+1;
	}
	}
	}
	}

	if( maxLen > 0 )
	return input.substr( maxStart, maxLen);
	return "";
	}
	void Test()
	{
	cout << "0 -> " << longestBalancedSubstr("0") << endl;
	cout << "1 -> " << longestBalancedSubstr("1") << endl;
	cout << "00 -> " << longestBalancedSubstr("00") << endl;
	cout << "11 -> " << longestBalancedSubstr("11") << endl;
	cout << "01 -> " << longestBalancedSubstr("01") << endl;
	cout << "10 -> " << longestBalancedSubstr("10") << endl;
	cout << "000 -> " << longestBalancedSubstr("000") << endl;
	cout << "111 -> " << longestBalancedSubstr("111") << endl;
	cout << "001 -> " << longestBalancedSubstr("001") << endl;
	cout << "010 -> " << longestBalancedSubstr("010") << endl;
	cout << "011 -> " << longestBalancedSubstr("011") << endl;
	cout << "100 -> " << longestBalancedSubstr("100") << endl;
	cout << "101 -> " << longestBalancedSubstr("101") << endl;
	cout << "110 -> " << longestBalancedSubstr("110") << endl;
	}
	int main()
	{
	string input;
	cin >> input;
	cout << longestBalancedSubstr(input) << endl;
	//Test();
	return 0;
	}

view raw LongestSubstringEqual01.cpp hosted with

by GitHub

Leave a Reply Cancel reply