algorithm - 在二进制字符串中找到包含相等数量的 0 和 1 的最大子字符串

Question

最近在一次采访中，我被要求编写一个程序来查找二进制字符串中包含相同数量的 0 和 1 的最大子字符串。

例如:

如果给定的字符串是 1010111 那么输出将是 1010 因为它包含 2 个 0 和 2 个 1s.

我尝试了很多，但还是想不出为这个东西建立一个算法。

有人可以告诉我如何继续或使用什么数据结构来解决这个问题吗？

Answer 1

以下将在 O(n) 时间和空间内工作，n 是字符串中的字符数。

• 跟踪当前 balance (或不平衡)1和 0你在 string 中看到过, 和 first字符串具有相同余额的时间(最多包含 n 个条目的数组或映射)
• 迭代string ，并且对于每个字符...
  • 更新balance , 计数 "1"作为1和 "0"作为-1反之亦然
  • 检查您何时(如果有的话)遇到相同的 balance之前
  • 如果差值大于当前best , 记住新的最长子串
  • 如果你还没有遇到那个余额，记住它是当前的 first职位

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

输出:

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}