python - 您可以在一个字符串中添加多少个字符 x 以使该字符串中不存在三个连续的字符？

Question

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

例子:

给定:猫

字符串:bbcbbabbbtbb输出: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

非常感谢任何帮助。

干杯

感谢最佳答案，如果有人想知道的话，我能够找到解决方案:

def consecB(S):
    num_of_b = S.count('b')
    return 2*((len(S)-num_of_b)+1) - num_of_b

Answer 1

我认为它比你做的要简单得多。

一个没有 b 开头的字符串，可以在每个字符之间插入两个 b，并在开头和结尾加上。 (根据字符串的长度，是多少？)

具有单个 b 的字符串在用 b“填充”时最终看起来与没有 b 在里面。所以就好像我们从一个短了 1 个字符的字符串开始(原来的 b 没有给我们额外的位置来插入它们)而且我们也可以少插入 1 个 b因为已经存在的那个将取而代之。因此，与字符不是 b 的情况相比，我们插入(练习:多少？)更少的 b。

这扩展到任意数量的孤立 b。

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

总而言之，一个简单的数学公式 - 根据字符串的长度和已经存在的 b 的数量 - 告诉我们答案。 (当然，如果已经有一个三元组 b 那么我们根本无法添加到字符串中，所以我们应该单独对其进行健全性检查)。