1888. 使二进制字符串字符交替的最少反转次数
给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：
- 类型 1 ：删除 字符串
s的第一个字符并将它 添加 到字符串结尾。 - 类型 2 ：选择 字符串
s中任意一个字符并将该字符 反转 ，也就是如果值为'0'，则反转得到'1'，反之亦然。
请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。
我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。
- 比方说，字符串
"010"和"1010"都是交替的，但是字符串"0100"不是。
提示：
- $1 <= s.length <= 10^5$
s[i]要么是'0'，要么是'1'。
思路
首先，目的是得到0101..或1010..样式的字符串。
类型1可以操作任意次，也就是说可以使用s+s的长度为 n 的子串和目标字符串进行比较。
使用cnt记录达到0101..需要进行的类型2操作数，n-cnt 就是达到0101..需要进行的类型2操作数。
每次向右滑动一位，出滑动窗口的字符与目标字符串对应位进行比较，若不同，则cnt–，因为之前记录时加入了修改用的操作数；进滑动窗口的字符与目标字符串对应位进行比较，若不同，同理，cnt++。
每滑一次，更新ans=min({ans,n-cnt,cnt})。
点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int minFlips(string s) {
int n = s.size();
string tar = "01";
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += (s[i] != tar[i % 2]);
}
int ans = min({cnt, n - cnt});
for (int i = 0; i < n; i++) {
cnt -= (s[i] != tar[i % 2]);
cnt += (s[i] != tar[(i + n) % 2]);
ans = min({ans, cnt, n - cnt});
}
return ans;
}
};
