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

Question

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

例如：

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

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

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

Answer 1

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

跟踪您在 string 和 first 中看到的 1 和 0 的当前 balance（或不平衡）字符串具有相同余额的时间（最多 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}

Answer 2

我会这样处理

初始化一个可变整数和并且maxlength = minimum
定义一个以总和为键，索引为值的哈希图
对于给定字符串中的每个值
- sum += arr[i] == 0 ?然后添加 -1 否则添加 1
- 如果总和为 0 maxlength = maxlength 或 index + 1 因为这是一个潜在的答案
- 否则，如果字典包含该总和值，则 maxlength = maxlength 或 (i -index hash[sum]) 较早发现的对结果有贡献的总和值。
- 如果 sum 的值不在哈希映射中，则更新哈希映射指数
- return最大长度。

这是我上面提到的示例，在代码中：working example 您可以尝试更改测试用例以查看这对各种测试用例的效果如何，也可以尝试打印哈希图并进行跟踪亲自动手，加深理解。

Answer 3

这个解决方案在优化方面不是最好的，但在面试的匆忙和压力下，这个解决方案可以快速思考、绘制和解释。

我会嵌套 2 个循环。

1从0开始到len - 2（递增）（最小长度应该是2）

1从len开始到上一个循环值+2（递减）（最小长度应该是2）

获取循环对应迭代器的子串

计算字符是否相等。

然后，如果为真，则与存储的结果长度进行比较，如果长度更大，则覆盖结果。

以 0100 为例，将针对这些值进行测试：

// result = ''
0100 //not balanced
010  //not balanced
01   //balanced AND length is greated than result's one. result = '01'
 100 //not balanced
 10  //balanced BUT length is not greated than result's one
  00 //not balanced

JavaScript 示例（我稍微调整了一下以优化迭代次数，但方法是相同的）：

var iterations = 0;

function IsBalanced(input, char1, char2)
{
    if (input.length % 2 != 0) // odd length can't be balanced
    {
      ++iterations;
      return (false);
    }
    let char1count = 0;
    let char2count = 0;
    let len = input.length;
    for (let i = 0; i < len; ++i)
    {
        ++iterations;
        if (input[i] == char1)
            ++char1count;
        else
            ++char2count;
    }
    return (char1count == char2count);
}

function findLargest(input, char1, char2)
{
    let len = input.length;
    let result = '';
    for (let k = 0; k < len - 1; ++k)
    {
        //        This is a tweak to reduce the number of iterations
        //  To avoid testing a substring smaller than the current result
        //                           |
        //                           |
        //                v----------------------v
        for (let l = len; l - k > result.length && l > k + 1; --l)
        {
            tempResult = input.substring(k, l);
            if (IsBalanced(tempResult, char1, char2) && tempResult.length > result.length)
                result = tempResult;
        }
    }
    return (result);
}

console.log("Input : 1010111 - result : " + findLargest("1010111", "1", "0") + " original size : " + "1010111".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : ababaaa - result : " + findLargest("ababaaa", "a", "b") + " original size : " + "ababaaa".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 00100100 - result : " + findLargest("00100100", "1", "0") + " original size : " + "00100100".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 1111100000 - result : " + findLargest("1111100000", "1", "0") + " original size : " + "1111100000".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 0001111111111010001111100000000001111111111 - result : " + findLargest("0001111111111010001111100000000001111111111", "1", "0") + " original size : " + "0001111111111010001111100000000001111111111".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 0000000000000000000000000000000000000000000000000001 - result : " + findLargest("0000000000000000000000000000000000000000000000000001", "1", "0") + " original size : " + "0000000000000000000000000000000000000000000000000001".length + " - iterations : " + iterations);

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

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

language-agnostic

algorithm