原文链接: https://leetcode-cn.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating

英文原文

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

• Type-1: Remove the character at the start of the string s and append it to the end of the string.
• Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

• For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

 

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

中文题目

给你一个二进制字符串 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. 题意理解（不含证明）
   1. 类型 1 和 类型 2 的操作顺序与最终答案无关，只与操作次数有关
   2. 按照 01 检测时需要修改的次数，用 len 减去就是按照 10 检测时修改的次数
2. 类型 1 的操作，其实是头尾相接，但是先删除再添加操作开销太大，并且操作很麻烦
3. 将字符串复制一份接在后面，即可使用滑动窗口丝滑拼接
4. 滑窗时减去离开的格子，加上进来的格子，即可避免大量重复计算
5. 答案就是滑窗过程中出现的最小修改次数

图解

{:width=”450px”}{:align=”left”}

{:width=”450px”}{:align=”left”}

优化

感谢评论区，实际上双倍字符串，只需要概念上理解一下，我们可以直接虚拟双倍

{:width=”500px”}{:align=”left”}

答题

[]
class Solution {
public:
    int minFlips(string s) {
        int len = s.size();
        string target = "01";

        int cnt = 0;
        for (int i = 0; i < len; i++) {
            cnt += (s[i] != target[i % 2]);
        }

        //s += s;
        int ans = min({ cnt, len - cnt });
        for (int i = 0; i < len; i++) {
            cnt -= (s[i] != target[i % 2]);
            cnt += (s[i] != target[(i + len) % 2]);
            ans = min({ ans, cnt, len - cnt });
        }

        return ans;
    }
};

致谢

感谢您的观看，希望对您有帮助，关注我的 力扣个人主页，欢迎热烈的交流！

统计信息

通过次数	提交次数	AC比率
2886	8949	32.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言