algorithm - 具有最少 3 个连续相同字符的二进制子串的数量

Question

我正在学习算法，我正在尝试解决二进制子字符串的问题。

我只能想到蛮力策略。有没有可能以更好的方式做到这一点？

我将使用示例展示我的方法。

考虑以下二进制字符串

010001

答案是 6 => (2,4), (1,4), (0,4), (2,5), (1,5), (0,5)

我的做法：

1. 查找具有最少 3 个相同字符的子字符串。
2. 进入左右并计算结果。
3. 对具有最少 3 个相同字符的每个子字符串重复此操作。

我怎样才能做得更好？

标签： algorithm

Answer 1

首先，您不能在短时间内完成此操作，O(n)因为您必须扫描字符串以找到所有 3 个相同的运行。

但为了有趣，假设我们的字符串是0100111000010. 在单次扫描中，我们可以列出结束至少 3 个运行的所有位置。将字符串的开头计数为0，这些位置是7, 10, 11并且字符串的长度为 13。

我们能从中找到答案吗？

对于从到的5起始位置和从0到并包括到的7-3=4所有8结束位置（要非常小心潜在的栅栏错误！）我们包括第一次运行的 1。所以有。71340

对于从 to 的3起始位置和从5to 的10-3=7所有4结束位置10，13我们包括第一个000，而且12更多。

对于从 to 的1起始位置和从8to 的11-3=8所有3结束位置11，13我们包括第二个000，而且3更多。

因此答案是40 + 12 + 3 = 55。

你能概括这条线推理并编写一个程序吗？如果是这样，它将及时执行，O(n)这是最好的。