leetcode 2026-03-07 每日一练 - 使二进制字符串字符交替的最少反转次数

题目描述

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

给你一个二进制字符串 s，你可以按任意顺序执行以下两种操作任意次：

  • 类型 1：删除字符串 s 的第一个字符并把它追加到末尾。
  • 类型 2：选择字符串 s 中任意一个字符并将其反转（'0' 变 '1'，'1' 变 '0'）。

请返回让 s 变成交替字符串的前提下，类型 2 的最少操作次数。

我们称一个字符串是交替的，当且仅当任意相邻字符都不同。

示例 1：

  • 输入：s = "111000"
  • 输出：2

示例 2：

  • 输入：s = "010"
  • 输出：0

解题思路

核心观察

这题难点是“可以先做若干次轮转，再做翻转最小化”。

把字符串轮转看成在 s+s 里取一个长度为 n 的窗口：

  • ss := s + s
  • 每个长度为 n 的窗口，都对应 s 的一种轮转结果。

对于固定窗口，要变成交替串只需要比较两种目标模式：

  • 以 0 开头：010101...
  • 以 1 开头：101010...

窗口中与目标串不一致的位置数，就是需要翻转的次数。

滑动窗口做法

  1. 预构造长度 2n 的两个目标串 target0、target1。
  2. 先统计第一个窗口 [0, n-1] 与两目标串的差异数 diff0、diff1。
  3. 滑动窗口右移：
    • 移出左侧字符，更新 diff0/diff1
    • 移入右侧字符，更新 diff0/diff1
  4. 每个窗口答案是 min(diff0, diff1)，全局取最小。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
func minFlips(s string) int {
    n := len(s)
    ss := s + s

    target0 := make([]byte, 2*n) // 以0开头的交替串：0101...
    target1 := make([]byte, 2*n) // 以1开头的交替串：1010...
    for i := 0; i < 2*n; i++ {
        if i%2 == 0 {
            target0[i] = '0'
            target1[i] = '1'
        } else {
            target0[i] = '1'
            target1[i] = '0'
        }
    }

    diff0, diff1 := 0, 0
    for i := 0; i < n; i++ {
        if ss[i] != target0[i] {
            diff0++
        }
        if ss[i] != target1[i] {
            diff1++
        }
    }

    // 初始答案为第一个窗口的最小值
    ans := int(math.Min(float64(diff0), float64(diff1)))

    // 滑动窗口：从n到2n-1
    for i := n; i < 2*n; i++ {
        // 移出窗口左侧的字符（i-n位置）
        leftIdx := i - n
        if ss[leftIdx] != target0[leftIdx] {
            diff0--
        }
        if ss[leftIdx] != target1[leftIdx] {
            diff1--
        }

        // 移入窗口右侧的新字符（i位置）
        rightIdx := i
        if ss[rightIdx] != target0[rightIdx] {
            diff0++
        }
        if ss[rightIdx] != target1[rightIdx] {
            diff1++
        }

        // 更新最小翻转次数
        currentMin := int(math.Min(float64(diff0), float64(diff1)))
        if currentMin < ans {
            ans = currentMin
        }
    }

    return ans
}

核心细节

  1. s+s 是关键，它把所有轮转统一成“固定长度窗口”。
  2. 每个窗口只看两种交替目标，不需要枚举翻转方案。
  3. diff0/diff1 通过“移出 + 移入”增量维护，避免重复统计。
  4. 代码里用了 math.Min，记得引入 math 包。

复杂度分析

  • 时间复杂度：O(n)
    • 构造目标串 O(n)
    • 初始化窗口 O(n)
    • 滑窗 O(n)
  • 空间复杂度：O(n)
    • ss、target0、target1 都是线性空间

示例分析

以 s = "111000" 为例：

  • 通过轮转可得到多个候选窗口（长度都为 6）。
  • 对每个窗口分别计算与 010101、101010 的差异。
  • 最优窗口下，最少只需翻转 2 位。

所以答案是 2。

总结

这题的标准解法是：

  • 把“轮转”转成“窗口”
  • 把“最少翻转”转成“与目标交替串的差异计数”
  • 用滑动窗口维护差异，做到线性时间