在一个字符串中可以添加多少个字符x，这样字符串中就不存在连续的三个字符了？

Question

这是一个leetcode式的面试问题，我试了一段时间，但没走多远，现在再试一次。给定一个字符串，您可以在字符串中输入多少个字符，例如“b”，这样字符串中就不存在连续的3个“b”。在

示例：

给定：cat

字符串：bbcbbabbtbb 输出：8

给定babb

字符串：bbabb 输出：1

给定bb

字符串：bb 输出：0

我的方法是用滑动窗口跟踪当前指数前面的“b”，但是我很快就迷路了。我的解决方案可能还很遥远，但在这里：

def consecB(S):
    num = 0

    for i in range(0, len(S)-2):
        if S[i] == 'b':
            if S[i+1] == 'b':
                pass
            else:
                num += 1
                str_list += 'b'
            num +=1
        else:
            if S[i+1] == 'b':
                if S[i+2] == 'b':
                    pass
                else:
                    num += 1
            else:
                num += 2

    return num

非常感谢任何帮助。在

干杯

多亏了上面的答案，如果有人想知道的话，我可以想出一个解决方案：

^{pr2}$

Answer 1

事实证明，一个洞察力让这件事变得微不足道。首先，检查字符串中是否已经有三个连续的bs；如果是这样，那么最后一个字符串必须通过基本测试。在

这样，最后的最大字符串将是b对作为分隔符和非b字符的书尾。所以。。。在

• 计算非b字符的数量；称为n。最后的字符串是n字符，加上2*(n+1)缓冲bs
• 添加到add的b的数量是2*(n+1) - (len(s) - n)，其中{}是原始字符串。在

Answer 2

我觉得这比你做的简单多了。在

一个没有b开头的字符串，可以在彼此的字符之间插入两个b，加在开头和结尾。（就绳子的长度而言，有多少根？）在

一个有一个b的字符串在用bs“填充”时看起来是一样的，就像它没有b一样。所以就好像我们从一个短了1个字符的字符串开始（原来的b没有给我们额外的插入位置），而且我们可以少插入1个b，因为已经存在的那个将取代它。因此，我们插入（练习：多少？）如果字符不是b，那么b要少。在

这扩展到任何数量的孤立的b

如果有一个双b，那么它将删除两个要插入的位置：比较插入acbbca和插入{}。无论哪种方式我们都得到bbabbcbbcbbabb；原理是一样的——我们从一个短2个字符的字符串开始，再少插入2个b，因为它们已经在那里了。也就是说，原始的b是孤立的还是折叠的并不重要；原始字符串中的每个b都会减少相同数量的答案。在

总之，一个简单的数学公式——根据字符串的长度和已经存在的b的数量——告诉我们答案。（当然，如果已经有一个三元组b，那么我们根本就不能添加到字符串中，所以我们应该单独检查它的合理性）。在