1888.使二进制字符串字符交替的最少反转次数：前缀和O(1)

【LetMeFly】1888.使二进制字符串字符交替的最少反转次数：前缀和O(1)

力扣题目链接：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 <= 105
• s[i] 要么是 '0' ，要么是 '1' 。

解题方法：前缀和

如果没有操作1（字符串轮转），那么问题就变成了1758. 生成交替二进制字符串的最少操作数。

现在多了个操作1，有什么用呢？

例如110，把1往后轮转，就变成了101，就不用翻转操作了。

其实不难发现轮转操作只对字符串长度为奇数时候有效：

如果字符串长度为偶数的话，最终有效的1010要么由1010变来，要么由0101变来。总之就是最终的01交替字符串无论是经过怎样的轮转得来的，其轮转之前就一定是01交替字符串。

但是奇数长度的字符串就不一样了，奇数长度的01字符串首位字符相同，所以最终有效的01字符串首位字符一定相同（如10101），所以就可能是原有两个相邻相同元素拆开轮转得到的（如01101）

所以我们模拟这个“拆开的位置”就好了。对于奇数长度的字符串，先假设变成0开头0结尾：

具体来说，01101如果全部变成01010需要改变3次，从前到后遍历字符串，遍历过01后，若从此处拆开，相当于后面本来要变成010的三个字符要变成101，后面只需要变化len(101) - 3 = 0次就好了。

记下全部变成010需要反转的次数，然后从前到后遍历，记录下遍历到的位置为止变成010..需要反转的次数，那么后面变成101...需要的次数就是len(后面字符串长度) - (原本总反转次数 - 前面已经反转次数)

讨论过变成010后，变成101同理。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-08 11:41:56
 */
/*
01001001101
   3次右移
01001101010
   ||
01010101010

相当于
01001001101
      ||
01001010101
  --
01010101010
_         _
*/
class Solution {
public:
    int minFlips(const string& s) {
        int total = 0, n = s.size();
        for (int i = 0; i < n; i++) {
            total += s[i] % 2 == i % 2;
        }
        int ans = min(total, n - total);
        if (n % 2 == 0) {
            return ans;
        }
        for (int i = 0, now = 0; i < n; i++) {
            now += s[i] % 2 == i % 2;
            int original_front = now;
            int original_back = total - original_front;
            int changed_front = i + 1 - original_front;
            int changed_back = n - i - 1 - original_back;
            ans = min(ans, min(original_front + changed_back, changed_front + original_back));
        }
        return ans;
    }
};

#if defined(_WIN32) || defined(__APPLE__)
/*
001000000010
|   | | |
101010101010

001000000010
    | | |
001010101010
-  右移一位
010101010100
   3次不可

4
*/
int main() {
    string s;
    while (cin >> s) {
        Solution sol;
        cout << sol.minFlips(s) << endl;
    }
    return 0;
}
#endif

解题方法二：滑动窗口

其实也可以把字符串double，然后定长滑动窗口len(s)，求每个窗口变成010或101的最小次数。

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源