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

🟠   🔖  字符串  🔗 力扣 LeetCode

题目

You are given a 0-indexed binary string s having an even length.

A string is beautiful if it's possible to partition it into one or more substrings such that:

• Each substring has an even length.
• Each substring contains only 1's or only 0's.

You can change any character in s to 0 or 1.

Return _theminimum number of changes required to make the string _sbeautiful.

Example 1:

Input: s = "1001"

Output: 2

Explanation: We change s[1] to 1 and s[3] to 0 to get string "1100".

It can be seen that the string "1100" is beautiful because we can partition it into "11|00".

It can be proven that 2 is the minimum number of changes needed to make the string beautiful.

Example 2:

Input: s = "10"

Output: 1

Explanation: We change s[1] to 1 to get string "11".

It can be seen that the string "11" is beautiful because we can partition it into "11".

It can be proven that 1 is the minimum number of changes needed to make the string beautiful.

Example 3:

Input: s = "0000"

Output: 0

Explanation: We don't need to make any changes as the string "0000" is beautiful already.

Constraints:

• 2 <= s.length <= 10^5
• s has an even length.
• s[i] is either '0' or '1'.

题目大意

给你一个长度为偶数下标从 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 <= 10^5
• s 的长度为偶数。
• s[i] 要么是 '0' ，要么是 '1' 。

解题思路

1. 遍历二进制字符串：

   • 遍历给定的二进制字符串 s，并对每一对相邻字符进行检查。
   • 由于“美丽的”字符串要求每一对相邻字符相同，因此我们可以从索引 0 开始，每次检查当前字符和下一个字符（即检查 s[i] 和 s[i + 1]）是否相同。

2. 判断相邻字符是否不同：

   • 如果相邻的字符 s[i] 和 s[i + 1] 不同，说明需要进行一次修改，改变其中一个字符使其与另一个字符相同，增加修改次数 res。

3. 跳过两个字符：

   • 每次检查两个字符（即每隔一个字符进行检查），因为我们是在处理相邻的字符对，因此可以通过 i += 2 来跳过已检查的字符对。

4. 返回结果：

   • 最后返回修改次数 res，即最少的修改次数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，需要遍历一遍字符串。
• 空间复杂度：O(1)，只使用了常数空间来存储修改次数。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minChanges = function (s) {
	let res = 0;
	for (let i = 0; i < s.length; i += 2) {
		if (s[i] !== s[i + 1]) {
			res++;
		}
	}
	return res;
};