二进制字符串转交替串最小操作数代码超时问题求解

原代码超时的核心原因是每次遇到相邻字符相同时，都实际执行了子串翻转操作，这一步时间复杂度为O(n)，整体算法时间复杂度达到O(n²)，当n较大（比如1e5级别）时必然触发超时。

优化思路 #

不需要真的修改字符串，通过记录翻转状态模拟翻转操作，将时间复杂度降至O(n)：

• 交替字符串只有两种可能：以0开头的0101...，或以1开头的1010...。
• 对每种目标交替串，遍历原字符串时用一个变量记录当前翻转状态（奇数次翻转等价于一次翻转，偶数次等价于无翻转）。
• 对比当前字符（原字符结合翻转状态后的实际值）与目标字符，若不一致则执行一次翻转操作（操作数+1，翻转状态取反）。
• 最终取两种目标串所需操作数的最小值。

优化后的代码 #

def min_operations(s, start_char):
    flip = 0
    count = 0
    target = start_char
    for c in s:
        # 计算当前实际字符：原字符经过flip次翻转后的结果
        current = '1' if (c == '0' and flip) or (c == '1' and not flip) else '0'
        if current != target:
            count += 1
            flip ^= 1  # 翻转状态取反
            # 翻转后下一个目标字符也会被翻转，直接切换target
            target = '1' if target == '0' else '0'
        else:
            # 目标字符正常切换
            target = '1' if target == '0' else '0'
    return count

for _ in range(int(input())):
    n = int(input())
    s = input().strip()
    # 计算转为两种交替串的操作数，取最小值
    res1 = min_operations(s, '0')
    res2 = min_operations(s, '1')
    print(min(res1, res2))

代码说明 #

• min_operations函数计算字符串转为以指定字符开头的交替串所需操作数：
  • flip变量记录当前翻转状态（0=未翻转，1=翻转奇数次）。
  • 遍历每个字符时，先计算经过翻转后的实际字符，再与目标字符对比。
  • 若不一致，执行翻转操作（操作数+1，翻转状态取反），同时目标字符因翻转同步切换。
• 主逻辑分别计算两种目标串的操作数，取最小值即为最终答案。

内容的提问来源于stack exchange，提问作者Aayush Puri