LeetCode 题解工作台
使二进制字符串变美丽的最少修改次数
给你一个长度为偶数下标从 0 开始的二进制字符串 s 。 如果可以将一个字符串分割成一个或者更多满足以下条件的子字符串，那么我们称这个字符串是 美丽的 ： 每个子字符串的长度都是 偶数 。 每个子字符串都 只 包含 1 或 只 包含 0 。 你可以将 s 中任一字符改成 0 或者 1 。 请你返回让…
1
题型
5
代码语言
3
相关题
当前训练重点
中等 · String-driven solution strategy
答案摘要
我们只需要遍历字符串 的所有奇数下标 $1, 3, 5, \cdots$，如果当前奇数下标与前一个下标的字符不同，即 $s[i] \ne s[i - 1]$，那么就需要修改当前字符，使得 $s[i] = s[i - 1]$。因此，此时答案需要加 。 遍历结束后，返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
给你一个长度为偶数下标从 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 <= 105s的长度为偶数。s[i]要么是'0'，要么是'1'。
解题思路
方法一：计数
我们只需要遍历字符串 的所有奇数下标 ，如果当前奇数下标与前一个下标的字符不同，即 ，那么就需要修改当前字符，使得 。因此，此时答案需要加 。
遍历结束后，返回答案即可。
时间复杂度 ，其中 是字符串 的长度。空间复杂度 。
class Solution:
def minChanges(self, s: str) -> int:
return sum(s[i] != s[i - 1] for i in range(1, len(s), 2))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidate should focus on understanding the partition structure of the string and identifying the minimal changes needed.
- question_mark
Look for the candidate's ability to implement the greedy approach efficiently, ensuring they avoid unnecessary operations.
- question_mark
Assess if the candidate correctly handles edge cases, such as strings that are already beautiful.
常见陷阱
外企场景- error
Failing to recognize that every part of the partition must have an even number of identical characters.
- error
Overcomplicating the problem by making unnecessary changes to characters when fewer are sufficient.
- error
Not handling cases where the string is already beautiful and no changes are needed.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle odd-length strings, exploring how the partition strategy changes.
- arrow_right_alt
Increase the complexity by requiring multiple partitions with different size constraints for each segment.
- arrow_right_alt
Extend the problem to allow for partitions based on different grouping strategies, such as alternating blocks of 0s and 1s.