分割均衡字符串
题目背景
在华为 OD 机试中，字符串处理是高频考点之一。这道题考察的是对'均衡'概念的理解以及贪心算法的应用。
问题描述
所谓均衡串，是指字符串中只包含两种字符，且这两种字符的出现次数完全相同。例如 XXYY 是均衡的，但 XYY 不是。
给定一个已经满足整体均衡条件的字符串，我们需要将其尽可能多地分割成新的均衡子串。目标是求出能分割出的最大个数。
解题思路
要得到最大分割数，直觉上应该尽早完成一次分割。也就是说，只要当前前缀中两种字符的数量相等，就应该立刻切一刀。这就是典型的贪心策略。
具体做法如下：
- 初始化计数器，记录当前遇到的两种字符数量差。
- 从左到右遍历字符串，遇到第一种字符加一，第二种减一（或者分别计数）。
- 一旦差值为零，说明从上次分割点到当前位置构成了一个均衡子串，结果加一。
- 继续遍历直到结束。
这种方法的正确性在于，如果存在一个更长的均衡子串包含了当前的平衡点，那么将其拆分为两个较小的均衡子串显然能得到更大的总数。因此，局部最优即全局最优。
代码实现
下面给出基于 Python 的实现方案。为了清晰起见，我们假设输入字符串只包含 'X' 和 'Y'。
def balancedStringSplit(s: str) -> int:
balance = 0
count = 0
for char in s:
if char == 'X':
balance += 1
else:
balance -= 1
# 一旦平衡归零，说明找到了一个最小的均衡段
if balance == 0:
count += 1
return count
# 测试用例
if __name__ == "__main__":
test_str = "XXYYXYXY"
print(balancedStringSplit(test_str)) # 输出应为 3
注意这里用 balance 变量来替代两个独立的计数器，逻辑更简洁。当 balance 回到 0 时，意味着正负抵消，两种字符数量相等。
复杂度分析
- 时间复杂度：O(n)，只需遍历一次字符串。
- 空间复杂度：O(1)，仅使用了常数个辅助变量。