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

难度: Medium

给你一个二进制字符串 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⁵
s[i] 要么是 '0' ，要么是 '1' 。

Submission

运行时间: 148 ms

内存: 16.4 MB

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        _s = "10" * (n // 2) + "1" * (n % 2)
        count = 0
        for i in range(n):
            if s[i] == _s[i]:
                count += 1
        if n % 2 == 0:
            return min(count, n-count)
        res = n
        for c in s:
            if c == "1":
                count = n - (count - 1)
            else:
                count = n - (count + 1)
            res = min(res, count, n-count)
        return res

Explain

首先，题解构造了一个理想的交替二进制字符串 `_s`，长度与 `s` 相同，开始以 '10' 交替。接着，题解通过遍历字符串 `s` 与 `_s` 对比，计算与 `_s` 匹配的字符数 `count`。如果 `s` 的长度 `n` 是偶数，直接返回 `min(count, n-count)`，因为可以通过 `count` 次反转得到 `_s` 或者通过 `n-count` 次反转得到 `_s` 的反向交替字符串。如果 `n` 是奇数，通过滑动窗口方式不断旋转字符串并计算最小反转次数，对于每个字符，根据它的值修改 `count`，并不断更新结果 `res` 为最小反转次数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)  # 获取字符串长度
        _s = '10' * (n // 2) + '1' * (n % 2)  # 构建理想的交替字符串
        count = 0
        for i in range(n):  # 计算与理想交替字符串匹配的字符数
            if s[i] == _s[i]:
                count += 1
        if n % 2 == 0:  # 如果长度为偶数，直接返回最小反转次数
            return min(count, n - count)
        res = n  # 初始化最小反转次数为 n
        for c in s:  # 遍历每个字符，模拟字符串的旋转操作
            if c == '1':
                count = n - (count - 1)  # 更新 count
            else:
                count = n - (count + 1)
            res = min(res, count, n - count)  # 更新最小反转次数
        return res

Explore

选择 '10' 或 '01' 作为交替字符串的起始模式实际上是任意的，因为它们都可以表示完整的交替模式。选择 '10' 只是一个设计选择，而且无论选择哪一个，最终的算法逻辑和结果都应该是等价的。选择 '10' 可能是因为在实现时首先考虑了以 '1' 开始的序列，然后紧跟 '0'，这不会影响最小反转次数的计算。

在偶数长度的字符串中，由于字符串长度正好可以完全匹配一次完整的交替模式（如 '10' 重复），这意味着理想的交替字符串和它的反向交替（如 '01' 开始）都是有效的目标字符串。`count` 表示与原始交替字符串匹配的字符数，而 `n - count` 表示与反向交替字符串匹配的字符数。因此，`min(count, n - count)` 表示将输入字符串转换为任一有效交替模式所需的最小反转次数。

对于奇数长度的字符串，算法通过模拟旋转来寻找最小反转次数。在代码中，旋转通过在循环中逐一考虑将字符串的首字符移动到尾部的情况来模拟。每次旋转，我们需要更新与理想交替字符串 `_s` 的匹配字符数 `count`。因为每次旋转实际上是将当前字符串的第一个字符移到最后，我们根据这个被移动字符是 '1' 还是 '0' 来相应地调整 `count`。通过这种方式，我们能够在每次模拟旋转后得到新的匹配数，并不断更新最小反转次数。

这些更新公式用于正确地计算在将字符串首字符旋转到末尾后，与理想交替字符串匹配的字符数。当旋转字符是 '1' 时，我们使用 `count = n - (count - 1)`，这是因为原来的 `count` 包括了这个 '1'，旋转后它不再在首位因此要减去1，然后求与非匹配字符的总数（`n - count`）。相反，如果是 '0'，我们使用 `count = n - (count + 1)`。这些操作都是为了保持 `count` 变量准确反映当前字符串与理想交替字符串 `_s` 的匹配程度。这种方法适用于所有字符旋转的情况，确保我们可以正确地更新匹配数。