Longest substring with equal number of 0s and 1s

Problem solving with programming: 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".

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 same 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).

Method 2: Efficient O(n) approach

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.

Or we can just use HashMap.

//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 "";


}

//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 "";


}

Read full article from Problem solving with programming: Longest substring with equal number of 0s and 1s