我们将二进制字符串0翻转为1，1翻转为0，但是在我的代码中超出了时间限制问题来了如何解决？

Question

for _ in range(int(input())):
    n=int(input())
    s=input()
    c=0
    for i in range(1,n):
        if s[i]==s[i-1]:
            c+=1
            t=s[i:]
            k=s[:i]
            for i in t:
                if i=='0':
                    k+='1'
                else:
                    k+='0'
            s=k
        else:
            pass
    print(c)

给定一个长度为 N 的二进制字符串 𝑆。您可以执行 对其进行以下操作：选择一个索引 i (1≤i≤N)，并翻转每个 S的字符从索引i到N。翻转一个字符意味着翻转 它从0到1，反之亦然。例如，如果 S=1001101 并且您 选择i=4，得到的字符串将为S=1000010。找到最小值 将 S 转换为交替字符串所需的操作数。 S 如果 s[i] 不等于 S[ i−1]，则称为交替串 每个 i 从 2 到 N。

但是在我的代码中出现了超过时间限制的问题，如何解决？

Answer 1

通过一次执行所有检查来降低时间复杂度。

从问题描述来看：

S is said to be an alternating string if s[i] not equal to S[i−1] for every i from 2 to N.

这意味着如果

S[i] == S[i - 1]

需要翻转。

任务是：

Find the minimum number of operations required to turn S into an alternating string.

在以下代码中：

• alternate

  字典将'1'映射到'0'和'0'映射到'1'，它用于翻转字符。

• prev

  被初始化为字符串

  S

  的第一个字符，它代表遇到的前一个字符。

• 该算法从第二个字符（索引 1）开始迭代字符串 S。

• 在每一步中，当前字符

  S[i]

  都会与前一个字符

  prev

  的值进行比较。

• 如果字符匹配，则

  flip

  计数递增，并且

  prev

  的值更改为备用值。这模拟了在执行下一次迭代之前翻转

  S[i]

  的值。

• 否则，

  prev

  将被赋予

  S[i]

  的值。

def flips_to_alternate(S):
    # Count the number of flips needed to make S alternating
    flips = 0
    alternate = {"1": "0", "0": "1"}
    # Initialise `prev` to `S[i - 1]`
    prev = S[0]
    for i in range(1, len(S)):
        if S[i] == prev:
            prev = alternate[S[i]]
            flips += 1
        else:
            prev = S[i]

    return flips