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

Question

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 ?

Answer 1

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}  # map or array; 0th element is 0
balance = 0     # initially, 1 and 0 are balanced
best = ""       # best substring found
for i, c in enumerate(string):             # (i, c) = (index, character)
    balance += 1 if c == "1" else -1       # update balance
    if balance not in first:               # first time we see this balance?
        first[balance] = i+1               # add next(!) position to map/array
    elif i - first[balance] > len(best):   # otherwise, if new longest substring
        best = string[first[balance]:i+1]  # update best with slice of string
    print(i, c, balance, best, first)      # debugging/demo output

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}