题目描述
思路解析
一句话答案：LeetCode 1888 使二进制字符串交替的最少反转次数：轮转不计、只数反转。s 拼成两倍长、滑宽 n 的窗口罗列所有轮转，每窗对标尺 0101 数出红格数，绿 = n - 红，红绿取小再全窗取 min。时间 O(n)、空间 O(1)。
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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:轮转 = 在两倍长串上滑长度 n 的窗口;铺固定标尺 0101…,红 = 和标尺不同的位数 = 改成标尺那种交替的反转数,绿 = n 减红 = 改成另一种交替的反转数。每个旋转取 min(红,绿),全局取最小。
第 1 步 · 把 s 接成两倍长：先动手准备。把 s = "11100" 复制一份接在自己后面,拼成一个两倍长的串 "1110011100",一共十个格子。为什么要拼两倍?因为轮转就是把开头的字符搬到末尾,在这个两倍长的串上,一个长度为 5 的窗口从左滑到右,依次框住的正好就是 s 的每一种轮转。现在整排先都灰着,还没开始比。
第 2 步 · 铺固定标尺 0101010101：再铺一把固定的标尺 "0101010101",按位置摆:偶数位要 0、奇数位要 1。把两倍长串每个格子和它正下方的标尺比一比,不同的标红,相同的标绿。红色格子就是「想让这段贴合标尺那种交替」必须反转的位;绿色格子是已经对上标尺的位。等会儿窗口框到哪儿,我们就只数窗口里的红和绿,窗口外的先不管。
旋转 0 · 窗口框住 [0,4]：让长度为 5 的窗口先框住最左边的 [0,4],这段就是原串 "11100" 本身,也就是「一次都不轮转」的那种情况。窗口外的格子先灰掉、不参与计数。第一个旋转我们一格一格仔细比,后面几个就能靠增量偷懒了。
旋转 0 · 逐格比对第 0 格：看第 0 格,它是 "1",正下方标尺要的是 "0"。两个不一样,标红,累计红到 1 个。继续看下一格。
旋转 0 · 逐格比对第 1 格：看第 1 格,它是 "1",正下方标尺要的是 "1"。两个一样,标绿,红仍是 1 个。继续看下一格。
旋转 0 · 逐格比对第 2 格：看第 2 格,它是 "1",正下方标尺要的是 "0"。两个不一样,标红,累计红到 2 个。继续看下一格。
旋转 0 · 逐格比对第 3 格：看第 3 格,它是 "0",正下方标尺要的是 "1"。两个不一样,标红,累计红到 3 个。继续看下一格。
旋转 0 · 逐格比对第 4 格：看第 4 格,它是 "0",正下方标尺要的是 "0"。两个一样,标绿,红仍是 3 个。五格比完,红一共 3 个。
旋转 0 · 绿 = 2,最优 = 2：红数完是 3,绿就是 n 减红,5 减 3 等于 2。绿的含义是:把这段改成「另一种交替串 10101」要反转 2 位。一个旋转的最优,就是红和绿里较小的那个,min(3,2) 等于 2。这是第一个旋转,先把全局最少 ans 记成 2,后面看能不能更小。
旋转 1 · 窗口滑到 [1,5]：窗口向右滑一格,来到 [1,5]。这一格代表把开头轮转掉 1 次后的串 "11001"。滑动时,原来在窗口头部第 0 格的字符离开了,末尾第 5 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 1 · 增量算红 = 2：增量更新红。离开的第 0 格有和标尺不同,所以红减 1;新进来的第 5 格没和标尺不同,红加 0。上一个窗口红是 3,这样一减一加,现在红是 2。只动两格、常数时间,这就是滑窗省力的地方。
旋转 1 · 最优 2 → ans 2：绿是 5 减 2 等于 3,这个旋转的最优 min(2,3) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
旋转 2 · 窗口滑到 [2,6]：窗口向右滑一格,来到 [2,6]。这一格代表把开头轮转掉 2 次后的串 "10011"。滑动时,原来在窗口头部第 1 格的字符离开了,末尾第 6 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 2 · 增量算红 = 3：增量更新红。离开的第 1 格没和标尺不同,所以红减 0;新进来的第 6 格有和标尺不同,红加 1。上一个窗口红是 2,这样一减一加,现在红是 3。只动两格、常数时间,这就是滑窗省力的地方。
旋转 2 · 最优 2 → ans 2：绿是 5 减 3 等于 2,这个旋转的最优 min(3,2) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
旋转 3 · 窗口滑到 [3,7]：窗口向右滑一格,来到 [3,7]。这一格代表把开头轮转掉 3 次后的串 "00111"。滑动时,原来在窗口头部第 2 格的字符离开了,末尾第 7 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 3 · 增量算红 = 2：增量更新红。离开的第 2 格有和标尺不同,所以红减 1;新进来的第 7 格没和标尺不同,红加 0。上一个窗口红是 3,这样一减一加,现在红是 2。只动两格、常数时间,这就是滑窗省力的地方。
旋转 3 · 最优 2 → ans 2：绿是 5 减 2 等于 3,这个旋转的最优 min(2,3) 等于 2。它没能小过之前的全局最少,所以 ans 保持在 2,继续往后滑看看。
旋转 4 · 窗口滑到 [4,8]：窗口向右滑一格,来到 [4,8]。这一格代表把开头轮转掉 4 次后的串 "01110"。滑动时,原来在窗口头部第 3 格的字符离开了,末尾第 8 格的字符进来了,紫色指的就是新进来的那一格。红绿不必从头重数,只要在上一个红值上改动一点点。
旋转 4 · 增量算红 = 1：增量更新红。离开的第 3 格有和标尺不同,所以红减 1;新进来的第 8 格没和标尺不同,红加 0。上一个窗口红是 2,这样一减一加,现在红是 1。只动两格、常数时间,这就是滑窗省力的地方。
旋转 4 · 最优 1 → ans 1：绿是 5 减 1 等于 4,这个旋转的最优 min(1,4) 等于 1。它比之前记的全局最少更小,于是把 ans 刷新成 1,我们找到了一种更省的旋转。
收束 · 最省旋转红 = 1：五个旋转全滑完。最省的落在窗口 [4,8],这段是 "01110",它和标尺只差 1 个红格,也就是只要反转 1 位就能变成交替串。全局最少 ans 就此定格在 1。
收束 · 反转 1 位 → 交替串：把最后那一个红格,第 6 格反转过来,这段就整整齐齐贴上了标尺,变成交替串 "01010"。全程只反转了 1 次,这就是答案。回头看,我们没有真的去反复轮转和重数,只是在两倍长串上滑一遍窗口、增量维护红值,线性时间就把最少反转数锁死了。
边界:本身交替答案为 0;偶数长度轮转不改变结果,只看原串 min(红,绿);"1110" 取绿 1、"0100" 取红 1,都是反转一位就成交替。
面试重点:两倍长串上滑长度 n 的窗口覆盖全部轮转;交替串只有两种,每个旋转取 min(红,绿)、绿 = n 减红;偶数长度轮转不改变答案,奇数长度才靠滑窗找更优,代码统一处理仍正确。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，n 是串长。第一遍数红扫一遍 O(n);第二遍模拟轮转也是 n 步,每步只做一减一加两次常数操作、再取一次最小,所以整体是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。关键是轮转后红值靠增量更新,绝不每换一个旋转就把整段重数一遍,否则会退化成 O(n 的平方)
- 空间：O(1)，按峰值算。只用了红值计数器 cnt 和答案 ans 两个整数,外加标尺常量 "01",都是常数个变量,不随 n 增长。注意「两倍长串」只是讲解用的思维模型,参考代码并不真的把串拼长,而是用下标对 2 取模的方式访问,所以额外空间是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么把 s 复制成两倍长,就能覆盖所有轮转?
追问为什么每个旋转要和固定标尺比、还要取 min(红,绿)?
追问奇数长度和偶数长度处理上有什么不同?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大交替子序列和
LeetCode 1911 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题