二进制字符串缩减

Question

给你一个长度为 n.
的二进制字符串（只有 0 和 1）s 您想通过执行最少次数的以下操作将 s 转换为空字符串。

在一个操作中，您可以从 s 中删除一个交替的子序列，而不改变其余字符的顺序。

你的任务是确定将 s 转换为空字符串所需的最少操作数。

注：

字符串s的交替子序列定义如下

任何长度为 1 的子序列
如果长度大于1，且没有两个连续元素相等。例如，'0101'、'101'、'0'是交替序列，而'100'和'01011'不是。

约束条件：

1 <= T <= 10
1 <= n <= 10^6

示例输入：

1
10
0100100111

示例输出：

解释：

从“0100100111”中删除子序列“010101”到设为“0011”

从“0011”中删除子序列“01”，使其成为“01”

最后，从“01”中删除子序列“01”，使其成为“”（空二进制字符串）

Answer 1

想象一下，对于某些字符串 x，您知道可以使用以“0”和 m 结尾的操作来删除它=39=]n 个以“1”结尾的操作，总共 (m+n) 个操作。我们将写这个（m，n）。这不一定是最好的结果，但它是一个的结果。

现在，您对字符串 x0 了解多少？

如果 n>1，那么你可以在其中一个以 1 结束的操作中添加一个零，将其变成一个以零结束的操作，这样你就可以清除 x0 (m+1,n-1) 次操作。

当然你总是可以添加一个 new 0 结束操作这样你就可以清除 x0 in (m+1, n) 操作。

类似地，您可以在 (m,n+1) 次操作中清除 x1，或者如果 m>0，则清除 (m-1,n+1)。

显然只有一种方法可以清除空字符串，那就是(0,0)操作，所以从头到尾，你可以计算出所有的各种(m,n)种可能性来清除每个前缀，直到你到达最后，然后总和最小的那个就是你的答案。那将是一个 O(n²) 算法。

但是，在没有的情况下，选择 (m+1,n) 而不是 (m+1,n-1) 将使您总体上使用更少的操作.同样，也不存在选择(m,n+1)优于(m-1,n+1)的情况。

因此，我们不必担心每个位置的两种可能选择，我们可以根据下一个字符是 0 还是 1，确定性地做出单个最佳选择：

从 x="" 和 (m,n) = (0,0) 开始：

当下一个字符为0时，则x <- x+"0" and (m,n) <- (m+1,max(n-1,0))
当下一个字符为1时，则x <- x+"1" and (m,n) <- (max(m-1,0),n+1)

当您到达字符串的末尾时，m+n 是可以清除它的最少操作次数。

或者，在伪代码中：

m = 0; n = 0;
for (char in string) {
    if (char == 0') {
        m = m+1;
        n = max(n-1,0);
    } else {
        m = max(m-1,0);
        n = n+1;
    }
}
return m+n;

简单易行。

二进制字符串缩减

Binary String Reduction

string

algorithm

data-structures

substring

subsequence