1888. 使二进制字符串字符交替的最少反转次数#

题目描述#

给你一个二进制字符串 s，你可以进行两类操作：

旋转：将第一个字符移动到末尾（可执行任意次）；
翻转：把一个字符 0↔1（可执行任意次）。

先做任意次旋转，再做任意次翻转。问：最少需要翻转多少次，才能让字符串变成相邻字符均不同（交替）。

示例：

1
输入：s = "111000"  → 输出：2
2
输入：s = "010"     → 输出：0
3
输入：s = "1110"    → 输出：1

解法思路#

核心思想：旋转 k 次等价于在环形数组上取一个长度为 n 的窗口。

把 s 复制一份拼成 s + s，则”旋转 k 次后再翻转”就等价于”在 s+s 上取起点为 l、长度 n 的窗口”，再把这个窗口翻成某个交替模式。交替模式只有两种：0101...（A）与 1010...（B）。

预处理 diff 数组：diff[i] = 1 当且仅当 s2[i] 与”以 0 开头、按全局下标奇偶”的目标位不同。即 diff[i] = (s2[i] != (i 为偶 ? '0' : '1'))。
对于起点 l 的长度 n 窗口，窗口内相对下标 0..n-1 的奇偶与全局下标 l..l+n-1 一致需满足 l 为偶数：
- l 为偶数时：翻成模式 A 的代价 = cur（窗口内 diff 之和），翻成模式 B 的代价 = n - cur；
- l 为奇数时：二者互换（用 flips = cur if l%2==0 else n-cur 统一表达，同时取 min(flips, n-flips) 覆盖两种模式）。
窗口整体每次右移一位，代价用 cur += diff[l+n] - diff[l] 在 O(1) 内更新。取所有窗口的最小值即可。

逐步举例（s = "111000"，n = 6）：

s2 = "111000111000"，diff（以 0 开头交替，'0'目标位为偶数下标）：i0:'1'→1, i1:'1'→0, i2:'1'→1, i3:'0'→1, i4:'0'→0, i5:'0'→1，前 6 位和 cur = 4。
l=0：flips = cur = 4，取 min(4, 6-4=2) = 2。即翻成模式 B 只需 2 次（把下标 1、3 两处对应的位翻掉）。后续所有窗口最小仍是 2，答案 2 ✓。

复杂度分析#

时间复杂度：O(n)，单次线性扫描。
空间复杂度：O(n)，diff 数组长度 2n。

代码实现#

1
class Solution:
2
    def minFlips(self, s: str) -> int:
3
        n = len(s)
4
        s2 = s + s
5
        diff = [0] * (2 * n)
6
        for i, ch in enumerate(s2):
7
            target = '0' if i % 2 == 0 else '1'
8
            diff[i] = 1 if ch != target else 0
9

10
        cur = sum(diff[:n])
11
        ans = n
12
        for l in range(n):
13
            flips = cur if l % 2 == 0 else n - cur
14
            ans = min(ans, flips, n - flips)
15
            cur += diff[l + n] - diff[l]
16
        return ans

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestMinFlips(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(self.solution.minFlips("111000"), 2)
15

16
    def test_example2(self):
17
        self.assertEqual(self.solution.minFlips("010"), 0)
18

19
    def test_example3(self):
20
        self.assertEqual(self.solution.minFlips("1110"), 1)
21

22
    def test_single_char(self):
23
        self.assertEqual(self.solution.minFlips("0"), 0)
24
        self.assertEqual(self.solution.minFlips("1"), 0)
25

26
    def test_already_alternating(self):
27
        self.assertEqual(self.solution.minFlips("01"), 0)
28
        self.assertEqual(self.solution.minFlips("10"), 0)
29
        self.assertEqual(self.solution.minFlips("0101"), 0)
30

31
    def test_all_same(self):
32
        self.assertEqual(self.solution.minFlips("000"), 1)
33
        self.assertEqual(self.solution.minFlips("111"), 1)
34
        self.assertEqual(self.solution.minFlips("0000"), 2)
35

36
    def test_longer(self):
37
        self.assertEqual(self.solution.minFlips("01001001101"), 2)
38

39

40
if __name__ == "__main__":
41
    unittest.main()