使二进制字符串字符交替的最少反转次数 图解题解

1888 到底要把这个二进制串折腾成什么样

串 s 只含 0 和 1。把开头字符移到末尾（整串向左轮转一格）不限次、不计入答案；任选一位取反不限次，但只数它。求变成交替串（相邻两位都不同）最少要几次取反。交替串只有 0101… 和 1010… 两种。题面 s = "010" 答案 0、"1110" 答案 1。

把每一种轮转都从头数一遍红格，会慢在哪

长度 n 的串最多有 n 个旋转，逐个和交替串逐位比、数出翻几位取最小，但每个旋转从头比是 n 次，合计 O(n²)（大 O 记号描述数据规模变大时操作数怎么涨），n 最大 10 的 5 次方、上百亿次跑不完；且相邻旋转中间一大段相同，每次白白重比。

轮转能转出的所有串，为什么全躲在 s+s 的一个滑窗里

把 s 复制一份接在自己后面拼成两倍长，取宽 n 的框从左往右一格格滑，框住的每段正好是 s 的一种旋转。这就是滑动窗口（固定宽度的框在序列上从左滑到右，每滑一步只在两端增删一个元素）。

s = "11100" 接成 "1110011100"，宽 5 的窗口依次框出 "11100"、"11001"、"10011"、"00111"、"01110" 五个旋转——最左是原串，右移一格即轮转一次。

一个窗口只数一次红，凭什么两种交替各要翻几位都知道了

两倍长串下面铺一把固定标尺 0101010101（偶数位 0、奇数位 1），窗口框住的段逐位和正下方比：不同记红、相同记绿，红数就是改成「标尺那种交替」要翻的位数。

另一种交替是把每位都取反，每个位置只能对上两种之一，红加绿恰好是 n，绿 = n - 红。每窗取红、绿较小者，全部窗口取最小即答案。数红还能增量：右移一格只有离开位、进入位变了，是红就各减 1、加 1。

拿 "11100" 把五个窗口的红绿亲手数一遍

首窗是原串 "11100"，对标尺段 01010 逐位比：1 对 0 红、1 对 1 绿、1 对 0 红、0 对 1 红、0 对 0 绿，红 3、绿 5 - 3 = 2，取 2，答案先记 2。右滑 "11001" 对 10101，红 2、绿 3，取 2。

再滑："10011" 对 01010 红 3、绿 2 取 2；"00111" 对 10101 红 2、绿 3 取 2；"01110" 对 01010 红只剩 1、绿 4 取 1，答案刷新成 1。把 "01110" 唯一的红位翻掉即交替串 01010。

只数红不看绿，"1110" 为什么会算成 3

"1110" 对标尺 0101 红是 3，把 3 当答案就错了：红只是「改成标尺那种」的代价，另一种是绿 = 4 - 3 = 1，翻一位成 1010 才最优。每窗都得红、绿取小，漏绿会系统性偏大；另一个反着错的是每滑一格整段重数，退回 O(n²)。

首窗数红 O(n)，此后每滑一格常数更新，整体 O(n)；只用红值、答案两个计数器，空间 O(1)，两倍长串不必真拼，下标取模访问（取模=除以长度取余数、绕回开头）。边界：串已交替（如 "010"）红处处 0、答案 0；n 为偶数时离开位与进入位奇偶相同、红值滑一圈不变，答案即原串与 0101、1010 差异较小者，像 "111000" 红 4、绿 2、答案 2。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        target = "01"
        cnt = sum(c != target[i & 1] for i, c in enumerate(s))
        ans = min(cnt, n - cnt)
        for i in range(n):
            cnt -= s[i] != target[i & 1]
            cnt += s[i] != target[(i + n) & 1]
            ans = min(ans, cnt, n - cnt)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minFlips(string s) {
        int n = s.size();
        string target = "01";
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] != target[i & 1]) {
                ++cnt;
            }
        }
        int ans = min(cnt, n - cnt);
        for (int i = 0; i < n; ++i) {
            if (s[i] != target[i & 1]) {
                --cnt;
            }
            if (s[i] != target[(i + n) & 1]) {
                ++cnt;
            }
            ans = min({ans, cnt, n - cnt});
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int minFlips(String s) {
        int n = s.length();
        String target = "01";
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != target.charAt(i & 1)) {
                ++cnt;
            }
        }
        int ans = Math.min(cnt, n - cnt);
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != target.charAt(i & 1)) {
                --cnt;
            }
            if (s.charAt(i) != target.charAt((i + n) & 1)) {
                ++cnt;
            }
            ans = Math.min(ans, Math.min(cnt, n - cnt));
        }
        return ans;
    }
}