Find the largest substring which contains equal number of 0s and 1s in a binary string

  • A+
Category:Languages

Recently in an interview I was asked to write a program to find the largest sub string which contains equal number of 0s and 1s in a binary string.

For example:

If the given string is 1010111 then the output will be 1010 as it contains 2 0s and 2 1s.

I tried a lot but can't come up with anyway to build an algorithm for this thing.

Can someone give me head start on how to proceed or what data structure to use for this problem ?

 


The following will work in O(n) time and space, n being the number of characters in the string.

  • keep track of the current balance (or imbalance) of 1 and 0 you've seen in the string, and the first time the string had the same balance (an array or map with at most n entries)
  • iterate the string, and for each character...
    • update the balance, counting "1" as 1 and "0" as -1 or vice versa
    • check when, if at all, you encountered the same balance before
    • if the difference is greater than the current best, remember the new longest substring
    • if you haven't encountered that balance yet, remember it's current first position

Example code in Python:

string = "1010111000" first = {0: 0} balance = 0 best = "" for i, c in enumerate(string):     balance += 1 if c == "1" else -1     if balance not in first:         first[balance] = i+1     elif i - first[balance] > len(best):         best = string[first[balance]:i+1]     print(i, c, balance, best, first) 

Output:

0 1 1  {0: 0, 1: 1} 1 0 0 10 {0: 0, 1: 1} 2 1 1 10 {0: 0, 1: 1} 3 0 0 1010 {0: 0, 1: 1} 4 1 1 1010 {0: 0, 1: 1} 5 1 2 1010 {0: 0, 1: 1, 2: 6} 6 1 3 1010 {0: 0, 1: 1, 2: 6, 3: 7} 7 0 2 1010 {0: 0, 1: 1, 2: 6, 3: 7} 8 0 1 01011100 {0: 0, 1: 1, 2: 6, 3: 7} 9 0 0 1010111000 {0: 0, 1: 1, 2: 6, 3: 7} 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: