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

sliding window, https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/

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

类型 1 ：删除 字符串 s 的第一个字符并将它添加到字符串结尾。
类型 2 ：选择 字符串 s 中任意一个字符并将该字符反转，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

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

我们称一个字符串是交替的，需要满足任意相邻字符都不同。

比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

提示：

1 <= s.length <= 10^5
s[i] 要么是 '0' ，要么是 '1' 。

问题：使二进制字符串字符交替的最少反转次数（类型 2 操作），允许任意次类型 1 操作（即把开头字符移到末尾）。

核心思路

我们要找到一种 旋转方式（通过类型1操作），使得在该旋转下，将字符串变为交替串所需的 翻转次数（类型2操作）最少。

什么是交替串？

以 '0' 开头："010101..." → 我们称这种为模式 A。
以 '1' 开头："101010..." → 我们称这种为模式 B。

对于一个固定字符串 s，我们可以计算它与模式 A 和模式 B 各自不同的位置数（即需要翻转的次数）。

但由于我们可以做任意次 类型1操作（旋转），所以我们要考虑所有可能的旋转情况，找出最小翻转次数。

但注意：直接枚举所有旋转（O(n) 种），每种 O(n) 计算翻转次数 → 总复杂度 O(n²)，会超时（n ≤ 1e5）。

所以我们需要用 滑动窗口 + 预处理 的技巧，做到 O(n)。

关键观察

类型1操作相当于把字符串变成它的某个循环移位。
我们可以把 s 复制一份接到后面，得到 ss = s + s，那么所有长度为 n 的子串 ss[i:i+n] 就代表了所有可能的旋转。
但我们不需要真的检查每一个子串，而是用滑动窗口动态维护当前窗口与两个目标模式（A/B）的差异。

但是目标模式是无限交替的，怎么对齐？

注意：当我们旋转字符串时，目标模式的起始字符也可能变化。例如，原串长度为偶数时，旋转不会改变奇偶位置的对应关系；但如果长度是奇数，旋转一次会导致原本匹配模式 A 的位置现在要匹配模式 B！

因此，我们需要分情况讨论：

分情况：n 是偶数 vs 奇数

情况1：n 是偶数

无论怎么旋转，奇数位和偶数位的数量不变。
所以目标模式 A（0101...）和 B（1010...）在整个旋转过程中结构不变。
因此，我们只需计算原始 s 与 A、B 的差异数，取最小即可？不对！ 因为我们可以通过旋转改变哪些字符在奇/偶位置。
但其实：对于偶数长度，任何旋转后的字符串，其奇偶位置上的字符集合仍然是原串的一半奇一半偶，只是顺序变了。
更重要的是：在偶数长度下，模式 A 和 B 是互补的，且旋转不会让一个原本匹配 A 的串变成更匹配 B。
实际上，在偶数长度时，所有旋转中，最小翻转次数 = min( diff_A, diff_B )，其中 diff_A 是原串与模式 A 的差异数。

结论：当 n 为偶数时，无需考虑旋转，直接取 min(diff_A, diff_B) 即可。

情况2：n 是奇数

这时候，旋转会改变奇偶位置的分布。
例如，原串长度5，位置0,2,4是偶数位；旋转一次后，原位置1变成新位置0（偶数位），所以原来在奇数位的字符现在被要求符合偶数位的模式。
这意味着：每次旋转，相当于在目标模式中切换了起始字符。
因此，我们需要考虑所有旋转，并对每个旋转计算与两种模式的差异。

但我们可以用 滑动窗口 在 ss = s + s 上高效计算。

提交代码

python

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        if n % 2 == 0:
            diff0 = 0
            for i, char in enumerate(s):
                expected = '0' if i % 2 == 0 else '1'
                if char != expected:
                    diff0 += 1
            return min(diff0, n - diff0)
        else:
            ss = s + s
            flip0 = 0
            for i in range(n):
                expected = '0' if i % 2 == 0 else '1'
                if ss[i] != expected:
                    flip0 += 1
            ans = min(flip0, n - flip0)
            for i in range(n):
                # Remove ss[i]
                expected_out = '0' if i % 2 == 0 else '1'
                if ss[i] != expected_out:
                    flip0 -= 1
                # Add ss[i + n]
                expected_in = '0' if (i + n) % 2 == 0 else '1'
                if ss[i + n] != expected_in:
                    flip0 += 1
                ans = min(ans, flip0, n - flip0)
            return ans

时间复杂度：O(n)，空间 O(n)（因为 ss = s+s）

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

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