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

难度: Medium

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

Submission

运行时间: 38 ms

内存: 16.2 MB

class Solution:
    def minChanges(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(1,n,2):
            if s[i] != s[i-1]:
                ans += 1
        return ans

Explain

该题解的核心思路是检查字符串中相邻的字符是否相同。由于要求每个美丽子字符串只包含相同的字符且长度是偶数，我们可以将字符串视为由多个两个字符组成的子串来检查。对于每一个从索引1开始的奇数索引，如果它与前一个字符（偶数索引）不同，那么至少需要更改其中一个字符来确保这两个字符相同，从而使得从这个偶数索引开始的两个字符长的子串成为美丽的。通过这种方式，我们可以计算出整个字符串中需要修改的最小字符数，从而使整个字符串变为美丽的。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minChanges(self, s: str) -> int:
        n = len(s)  # 获取字符串的长度
        ans = 0  # 初始化修改次数为0
        for i in range(1, n, 2):  # 从索引1开始每隔一个元素检查，即检查所有奇数索引
            if s[i] != s[i-1]:  # 如果当前字符与前一个字符不同
                ans += 1  # 需要修改次数加1
        return ans  # 返回总的修改次数

Explore

选择从索引1开始，并每隔一个元素进行检查（即检查所有奇数索引），是因为我们的目标是确保每两个相邻的字符组成的子串都只包含相同的字符。在二进制字符串中，每两个字符可以形成一个长度为2的子串，对于从索引0开始的偶数索引和其后的奇数索引（如0和1，2和3）这种配对方式，需要检查这两个字符是否相同。通过这种方式，我们能够确保所有的字符对都满足条件，从而使整个字符串变得美丽。

在提出的解法中，我们是按每两个字符为一组进行检查和修改的。对于如 '111' 这样的字符串，我们按照索引检查（0和1，1和2），首先检查0和1时发现它们相同，不需要修改。然后检查1和2也发现它们相同，不需要修改。然而，根据题目要求，每个子字符串的长度必须是偶数，所以不能有长度为3的子字符串。在这种情况下，可以选择修改任何一个字符（比如中间的字符1改为0），使得字符串分割成两个长度为2的子字符串（如'10'和'01'），这样的修改次数最少。

题目已明确指出给定的二进制字符串长度为偶数，因此在这种情况下我们不需要考虑字符串长度为奇数的情况。如果在其他情况下遇到奇数长度的字符串，我们需要在设计算法时考虑如何处理最后一个无法配对的字符。可能的处理方法包括增加一个字符使其长度变为偶数，或者在某个位置上做出修改，使得所有子字符串的长度都为偶数。