求使二进制字符串有序所需的最少替换次数

核心思路是枚举所有可能的有序状态，计算每种状态的替换次数，取最小值。有序状态分为三类：

1. 全为0：需要把所有1替换成0，次数等于字符串中1的总数。
2. 全为1：需要把所有0替换成1，次数等于字符串中0的总数。
3. 前k个字符为0，剩余n-k个字符为1（k从1到n-1）：替换次数 = 前k个字符中1的数量（要换成0） + 剩余字符中0的数量（要换成1）。

为了高效计算，可以先预处理两个辅助数组：

• prefix_ones：prefix_ones[i]表示前i个字符中1的数量（i从0到n，prefix_ones[0]=0，prefix_ones[1]是第一个字符是否为1）。
• suffix_zeros：suffix_zeros[i]表示从第i个字符到末尾中0的数量（i从0到n，suffix_zeros[n]=0，suffix_zeros[n-1]是最后一个字符是否为0）。

然后遍历所有可能的分界点k（从0到n，k=0对应全1，k=n对应全0），计算prefix_ones[k] + suffix_zeros[k]，取这个值的最小值就是答案。

1. 统计字符串长度n，初始化前缀和数组prefix_ones，长度n+1：
   • prefix_ones[0] = 0
   • 从i=1到n：prefix_ones[i] = prefix_ones[i-1] + (1 if s[i-1] == '1' else 0)
2. 初始化后缀和数组suffix_zeros，长度n+1：
   • suffix_zeros[n] = 0
   • 从i=n-1到0：suffix_zeros[i] = suffix_zeros[i+1] + (1 if s[i] == '0' else 0)
3. 遍历k从0到n，计算每个k对应的替换次数cost = prefix_ones[k] + suffix_zeros[k]，记录最小的cost。

def min_flips(s):
    n = len(s)
    prefix_ones = [0] * (n + 1)
    for i in range(1, n+1):
        prefix_ones[i] = prefix_ones[i-1] + (1 if s[i-1] == '1' else 0)
    
    suffix_zeros = [0] * (n + 1)
    for i in range(n-1, -1, -1):
        suffix_zeros[i] = suffix_zeros[i+1] + (1 if s[i] == '0' else 0)
    
    min_cost = float('inf')
    for k in range(n+1):
        cost = prefix_ones[k] + suffix_zeros[k]
        if cost < min_cost:
            min_cost = cost
    return min_cost

# 测试示例
print(min_flips("0011110010"))  # 输出3
print(min_flips("0011110"))     # 输出1
print(min_flips("1010110111"))  # 输出3

你尝试用当前0的数量确定分界位置，这种方式只考虑了“最终0的数量等于原字符串0的数量”这一种情况，但实际上最优解可能不需要保留所有原0——比如示例"0011110"，原0数量是3，最优解是把最后一个0换成1（保留前2个0），而不是保留3个0（那样需要把中间的1换成0，次数更多）。所以必须枚举所有可能的分界点，而不是仅固定0的数量。

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