二进制字符串翻转段外区域求最大1数量及亚平方复杂度优化方案

问题描述 #

给定长度为n的二进制字符串（仅含0和1），需选择一段[i,j]（索引满足i≥0且j < n-1，即最后一个字符不能包含在该段中），执行一次操作：翻转0到i-1以及j+1到n-1区域的字符（0变1，1变0）。求操作后字符串中能得到的最大1的数量。

约束条件 #

• 2 ≤ n ≤ 10^5

示例 #

• 示例1：输入s = "10000011"，选择段[6,6]，翻转剩余区域后得到"01111110"，结果为6。
• 示例2：输入s = "100110"，选择段[3,4]，翻转剩余区域后得到"011111"，结果为5。

需求 #

现有解法时间复杂度为O(n³)，需找到时间复杂度低于O(n²)的高效解法。

O(n)时间复杂度解法 #

思路推导 #

设原字符串总1的数量为total_ones，通过数学推导可将问题转化为寻找最优[i,j]组合：

操作后的总1数可拆解为三部分：

1. 段[i,j]的1数保持不变，记为count_ones(i,j)
2. 前缀[0,i-1]翻转后的1数 = 前缀长度 - 前缀原1数
3. 后缀[j+1,n-1]翻转后的1数 = 后缀长度 - 后缀原1数

将三者合并化简后，操作后的总1数可表示为：

总1数 = 2*count_ones(i,j) + i - j + (n-1) - total_ones

进一步变形，引入前缀和current_sum（前k个字符的1数），可将目标转化为最大化：

(2*current_sum[k] - k) + (-2*current_sum[i] + i) + 1

其中k = j+1（j ≤ n-2 → k ≤ n-1），且i < k。

遍历每个k时，只需维护前k个位置中-2*current_sum[i] + i的最大值，即可快速计算当前k对应的最优候选值，最终得到全局最大值。

具体步骤 #

1. 统计总1数：遍历字符串，统计原字符串中1的总数total_ones。
2. 初始化变量：
   • current_sum：实时计算前缀和，初始为0
   • max_left_val：维护-2*current_sum[i] + i的最大值，初始为0（对应i=0的情况）
   • max_term：记录推导式中的最大值，初始为负无穷
3. 遍历计算：
   遍历k从1到n-1：
   • 更新前缀和current_sum，加上第k-1位字符的数值
   • 计算当前右侧值current_right_val = 2*current_sum - k
   • 计算当前候选值candidate = current_right_val + max_left_val + 1，更新max_term
   • 计算当前位置的current_val = -2*current_sum + k，更新max_left_val
4. 计算最终结果：max_term + (n-1 - total_ones)

代码实现（Python） #

def max_ones_after_operation(s):
    n = len(s)
    total_ones = s.count('1')
    current_sum = 0
    max_left_val = 0  # val[0] = -2*0 +0=0
    max_term = float('-inf')
    
    for k in range(1, n):
        current_sum += int(s[k-1])
        current_right_val = 2 * current_sum - k
        candidate = current_right_val + max_left_val + 1
        if candidate > max_term:
            max_term = candidate
        current_val = -2 * current_sum + k
        if current_val > max_left_val:
            max_left_val = current_val
    
    return max_term + (n-1 - total_ones)

复杂度分析 #

• 时间复杂度：O(n)，仅需两次线性遍历（一次统计总1数，一次遍历计算最优值）
• 空间复杂度：O(1)，仅使用常数额外空间

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