# 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 `0`s and `1`s in a binary string.

For example:

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

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} ``