解题思路

首先要知道在什么情况下，反异或可以节省1的个数，我们知道异或的结果是00-0，11-0，01-1，所以如果有类似1001这样的串，即对称的、且对称位置都是1的串，我们可以反异或后得到，比如1001用0001反异或得到，这样就节省了一半的1。但是这里要注意奇数个数的串，比如111，就不可以用011反异或得到，因为中间的1和1异或得到的是0。综上，题目的突破点就是，找到1的数量最多的回文子串，且如果是奇数串的话中间不能为1。

编码思路。 先求前缀和，解释一下前缀和是什么，有一个串s，我们要求前i个数据中有几个1，假设我们知道前i-1个数据中有多少个1，我们只要判断第i个字符是不是1，就可以直接计算出前i个数据的结果，类似数列的前n项和的概念。既然我们知道了前i个数据中有a个1，前j个数据中有b个1，那么从i+1到j中，有多少个1？b-a个1。知道了这个，我们在题目中判断某个区间有多少个1的时候，就不需要重复切片增加时间复杂度，否则会有几个测试点无法通过。 接下来要求1数量最多的回文子串，我们要知道怎么求最长回文子串。暴力的方法，就是以每个字符为中心往外扩张，这样的方法复杂度是n方。（涉及到奇数和偶数的问题，只需要在每个字符之间插入#就可以解决）改进的方法是manacher方法，这个方法的核心其实就是省去了一些冗余的操作，比方说一个串是axbxcxbxa，整个串是一个回文串，那么我们在计算第二个b的回文串长度时，我们已知第二个b和第一个b是关于c对称的，那么我们计算过c，从左到右我们肯定也计算过第一个b，这样第二个b我们就不用从头扩张，它的回文串长度可以从第一个b中得到一部分信息，可以减少复杂度。（具体的可以去找个视频学） 总结我们的方法，先计算前缀和数组pre，接着使用manacher算法，manacher循环的每一次操作，根据pre数组更新1最多的回文子串的长度，最后得到结果ones，将ones折半就是可以省去的数量，再和整个串1的数量做减法就是我们想要的答案了。

import os
import sys

# 请在此输入您的代码

def manacher(s):
    s = '#'+'#'.join(s)+'#'
    n = len(s)
    r = 0
    c = 0
    l = 0
    p = [0]*(n)
    ones = 0
    pre = [0]*(n+1)
    for i in range(1,n):
      pre[i] = pre[i-1] + (s[i]=='1')
    for i in range(n):
        if r>i:
            l = min(p[2*c-i],r-i)
        else:
            l = 1
        while i+l<n and i-l>=0 and s[i+l]==s[i-l]:
            l += 1
        if i+l>r:
            r=i+l
            c=i
        if s[i]!='1':
            ones = max(ones,pre[i+l-1]-pre[i-l+1])
        p[i]=l
    return ones

s = input().strip()
num = s.count('1')
sub = int(manacher(s)//2)
print(num-sub)
copy