华为 OD 机试：分割均衡字符串

分割均衡字符串

题目描述

• 均衡串定义：字符串中只包含两种字符，且这两种字符的个数相同。
• 给定一个均衡字符串，请给出可分割成新的均衡子串的最大个数。
• 约定：字符串中只包含大写的 X 和 Y 两种字符。

输入描述

• 输入一个均衡串。
• 字符串的长度：[2, 10000]。
• 给定的字符串均为均衡字符串。

输出描述

• 输出可分割成新的均衡子串的最大个数。

解题思路

采用贪心算法。遍历字符串，维护一个计数器 balance。遇到 'X' 加 1，遇到 'Y' 减 1。当 balance 为 0 时，说明当前遍历的部分是一个最小均衡子串，结果计数加 1。由于题目保证输入是均衡字符串，遍历结束时必然能完全分割。

代码实现

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

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串长度，只需遍历一次。
• 空间复杂度：O(1)，仅使用常数个变量。