跳转至

2914. 使二进制字符串变美丽的最少修改次数

题目描述

给你一个长度为偶数下标从 0 开始的二进制字符串 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" 是美丽的，因为它已经是美丽的。
将字符串变美丽最少需要 1 次修改。

示例 3：

输入：s = "0000"
输出：0
解释：不需要进行任何修改，字符串 "0000" 已经是美丽字符串。

 

提示：

  • 2 <= s.length <= 105
  • s 的长度为偶数。
  • s[i] 要么是 '0' ，要么是 '1' 。

解法

方法一：计数

我们只需要遍历字符串 $s$ 的所有奇数下标 $1, 3, 5, \cdots$，如果当前奇数下标与前一个下标的字符不同，即 $s[i] \ne s[i - 1]$，那么就需要修改当前字符，使得 $s[i] = s[i - 1]$。因此，此时答案需要加 $1$。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

1
2
3
class Solution:
    def minChanges(self, s: str) -> int:
        return sum(s[i] != s[i - 1] for i in range(1, len(s), 2))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minChanges(String s) {
        int ans = 0;
        for (int i = 1; i < s.length(); i += 2) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minChanges(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 1; i < n; i += 2) {
            ans += s[i] != s[i - 1];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minChanges(s string) (ans int) {
    for i := 1; i < len(s); i += 2 {
        if s[i] != s[i-1] {
            ans++
        }
    }
    return
}

1
2
3
4
5
6
7
8
9
function minChanges(s: string): number {
    let ans = 0;
    for (let i = 1; i < s.length; i += 2) {
        if (s[i] !== s[i - 1]) {
            ++ans;
        }
    }
    return ans;
}

评论