Medium
题目描述
给你一个长度为偶数的二进制字符串 s。
如果一个字符串可以被分割成一个或多个子字符串，使得：
- 每个子字符串的长度都是偶数。
- 每个子字符串只包含
1或只包含0。
那么我们称这个字符串是美丽的。
你可以将 s 中的任何字符更改为 0 或 1。
返回使字符串 s 变美丽所需的最小更改次数。
示例 1：
输入：s = "1001"
输出：2
解释：我们将 s[1] 更改为 1，将 s[3] 更改为 0，得到字符串 "1100"。
可以看出字符串 "1100" 是美丽的，因为我们可以将它分割为 "11|00"。
可以证明，使字符串变美丽所需的最少更改次数为 2。
示例 2：
输入：s = "10"
输出：1
解释：我们将 s[1] 更改为 1，得到字符串 "11"。
可以看出字符串 "11" 是美丽的，因为我们可以将它分割为 "11"。
可以证明，使字符串变美丽所需的最少更改次数为 1。
示例 3：
输入：s = "0000"
输出：0
解释：我们不需要进行任何更改，因为字符串 "0000" 已经是美丽的了。
约束条件：
2 <= s.length <= 10^5s的长度为偶数s[i]是'0'或'1'
解题思路
这道题的关键洞察是：为了让字符串变美丽，我们可以将字符串分解为长度为2的连续块，然后使每个块内的两个字符相同。
思路分析：
根据题目提示，任何有效的美丽分割都可以进一步分解为长度恰好为2的块。这是因为：
- 每个美丽的子字符串长度都是偶数且只包含相同字符
- 长度为偶数的相同字符串可以分解为多个长度为2的相同字符对
因此，我们可以采用贪心策略：
- 将字符串每两个字符分为一组
- 对于每组中的两个字符，如果它们不相同，我们需要修改其中一个
- 修改次数就是不相同的字符对数量
这种贪心策略是最优的，因为：
- 我们必须保证每个长度为2的块内字符相同
- 对于不同的字符对，最少需要1次修改
- 不同块之间的修改是独立的
算法步骤：
- 遍历字符串，每次跳跃2个位置
- 比较相邻的两个字符
- 如果不相同，计数器加1
- 返回总的修改次数
时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。
代码实现
class Solution {
public:
int minChanges(string s) {
int changes = 0;
for (int i = 0; i < s.length(); i += 2) {
if (s[i] != s[i + 1]) {
changes++;
}
}
return changes;
}
};
class Solution:
def minChanges(self, s: str) -> int:
changes = 0
for i in range(0, len(s), 2):
if s[i] != s[i + 1]:
changes += 1
return changes
public class Solution {
public int MinChanges(string s) {
int changes = 0;
for (int i = 0; i < s.Length; i += 2) {
if (s[i] != s[i + 1]) {
changes++;
}
}
return changes;
}
}
/**
* @param {string} s
* @return {number}
*/
var minChanges = function(s) {
let changes = 0;
for (let i = 0; i < s.length; i += 2) {
if (s[i] !== s[i + 1]) {
changes++;
}
}
return changes;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历字符串一次，其中 n 是字符串长度 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |