问题标签 [binary-string]

这是纳斯达克实习编码轮中提出的一个问题。

节目说明：

该程序将二进制字符串作为输入。我们必须连续删除所有字符交替的子序列，直到字符串为空。任务是找到这样做所需的最少步骤数。

示例1：
让字符串为：0111001
Removed-0101, Remaining-110
Removed-10 , Remaining-1
Removed-1
No of steps = 3

示例2 ：
让字符串为：111000111
Removed-101, Remaining-110011
Removed-101, Remaining-101
Removed-101
No of steps = 3

示例 3：
让字符串为：11011
Removed-101, Remaining-11
Removed-1 , Remaining-1
Removed-1
No of steps = 3

示例4 ：
让字符串为：10101
Removed-10101
No of steps = 1

我尝试的解决方案将二进制字符串的第一个字符视为我的子序列的第一个字符。然后创建一个新字符串，如果下一个字符不是交替序列的一部分，则将在其中附加下一个字符。新字符串成为我们的二进制字符串。以这种方式，循环继续，直到新字符串为空。（有点 O(n^2) 算法）。正如预期的那样，它给了我一个超时错误。在 C++ 中添加一个与我尝试过的代码有点相似的代码，它是用 Java 编写的。

我还尝试了诸如查找相同连续字符的最大子序列的长度之类的方法，这显然不能满足所有情况，例如 example3。

希望有人可以帮助我为这个问题提供最优化的解决方案。最好是 C、C++ 或 python 中的代码。甚至算法也可以。

假设 S 是一个只包含 0 和 1 的字符串。我想计算 S 的非空子字符串的数量，其中 0 的数量小于 1 的数量。

使用下面给出的蛮力方法，我们可以有一个算法在 O(n^2) 中解决这个问题：

但是我们能不能有一个更好的时间复杂度为 O(n*logn) 或 O(n) 的算法，并且空间复杂度是从 O(1) 到 O(n) 的任何值？

蟒蛇 3

我想通过套接字发送二进制字符串。我在用

socket.send(b"Hello from {0}",client_id)

但是我发现它没有正确替换clientid。

我究竟做错了什么？我这样做是在二进制字符串中完成的