algorithm - 在二进制字符串中查找最长的子字符串，其中不少于零

Question

如何在二进制字符串中找到平衡(即 1 和 0 的个数之差) >= 0 的最长子串？

例子:

01110000010 -> 6: 011100

1110000011110000111 -> 19: entire string

虽然这个问题看起来与 Maximum Value Contiguous Subsequence (Maximum Contiguous Sum) 非常相似问题，动态规划解决方案似乎并不明显。在分而治之的方法中，如何进行合并？毕竟“高效”的算法可能吗？ (一个简单的 O(n^2) 算法将迭代所有可能的起点的所有子串。)

这是 Finding a substring, with some additional conditions 的修改变体.不同之处在于，在链接的问题中，只有在余额永远不会低于零的情况下才允许使用此类子字符串(向前或向后查看字符串)。在给定的问题中，允许余额降至零以下，前提是它会在稍后的某个阶段恢复。

Answer 1

我有一个解决方案需要 O(n)额外的内存和 O(n)时间。

让我们表示索引的“高度”h(i)作为

h(i) = <number of 1s in the substring 1..i> - <number of 0s in the same substring>

问题现在可以重新表述为:find i和 j例如h(i) <= h(j)和 j-i -> max .

显然，h(0) = 0 , 如果 h(n) = 0 ，那么解就是整个字符串。

现在让我们计算数组B这样B[x] = min{i: h(i) = -x }.换句话说，让B[x]是最左边的索引 i h(i)= -x .

数组B[x]长度最多为 n , 并在一次线性传递中计算。

现在我们可以遍历原始字符串并为每个索引 i计算以 i 结束的具有非负余额的最长序列的长度如下:

Lmax(i) = i - B[MIN{0, h(i)}]

最大Lmax(i)所有 i会给你想要的长度。

我将证明留作练习 :) 如果您无法理解，请联系我。

此外，我的算法需要对原始字符串进行 2 次传递，但您可以将它们合并为一次。