Readme

1888.Minimum-Number-of-Flips-to-Make-the-Binary-String-Alternating

首先，flip和rotate两个操作彼此之间不会有任何影响。比如你有a次flip，b次rotate，那么打乱顺序去实现这a+b次操作，结果都完全一样。所以我们不妨考虑先做flip，再做rotate。言下之意，先做flip，然后将序列前端的某一段翻转之后拼在序列后端。

如果flip操作完之后已经是交替序列了，那么就不需要rotate。那么rotate能带来什么好处呢？唯一的好处就是类似这种情况：

0101 1010101

前后半段都是交替序列，但整体并不是交替序列，因为中间有两个连续的1.此时用flip再做调整显然是低效的。我们发现，如果我们将前面那段转移到后面去，就解决了这个问题。当然，能翻转的先决条件是，前端的头是0，后段的尾是1. 类似的，如果前段的头是1，后段的尾是0的话，也可以做这样的rotate，省下flip的操作。

这样来看，我们只要将前后两个序列各自弄成交替序列就行了。

那么如何确定这个分界点呢？自然想到会枚举一下这个位置。加入分界点在i和i+1的地方，这时候我们考虑的是：前段从左往右的0101序列，后段从右往左的1010序列，然后可以在这个地方断开rotate。或者前段从左往右的1010序列，后段从右往左的0101列，然后也可以在这点断开rotate。我们容易知道，可以用one pass计算从左往右0101序列延伸到每个位置时的flip操作数，同理也可以提前预处理从左往右1010序列延伸到每个位置时的flip操作数、从右往做0101序列延伸到每个位置时的flip操作数、从右往做1010序列延伸到每个位置时的flip操作数。

最终的答案就是枚举端点位置i，考察left0[i]+right1[i+1]和left1[i]+right0[i+1]的较小值。