刷题笔记合集🔗

分割均衡字符串

问题描述

均衡串定义：字符串中只包含两种字符，且这两种字符的个数相同。

给定一个均衡字符串，请给出可分割成新的均衡子串的最大个数。

约定：字符串中只包含大写的 和 两种字符。

输入格式

输入一个均衡串。

• 字符串的长度：。
• 给定的字符串均为均衡字符串

输出格式

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

样例输入

XXYYXY

样例输出

2

数据范围

• 字符串的长度：
• 给定的字符串均为均衡字符串，即字符串中 和 的数量相等
• 字符串中只包含大写的 和 两种字符

题解

这道题是关于字符串分割的问题，需要将一个均衡字符串分割成尽可能多的均衡子串。

首先理解什么是均衡子串：字符串中只包含两种字符（题目中是X和Y），且这两种字符的个数相同。分割后的子串需要是原字符串的连续子串。

思路很直接：从左往右扫描字符串，统计X和Y的出现次数。当X和Y的数量相等时，就说明找到了一个均衡子串。为了使分割的均衡子串数量最大，应该在满足X和Y数量相等的时候立即进行分割。

为什么这样做是正确的？因为如果继续扫描而不分割，后面即使能找到均衡子串，总数量也不会增加，反而可能减少。这是一个贪心策略，即一旦找到满足条件的最小均衡子串就立即分割。

例如对于样例"XXYYXY"：

1. 扫描到"XXYY"时，X和Y各2个，数量相等，找到第一个均衡子串
2. 剩下"XY"，X和Y各1个，数量相等，找到第二个均衡子串
3. 总共可以分割成2个均衡子串

算法的时间复杂度是O(n)，其中n是字符串的长度。我们只需要遍历一次字符串，统计X和Y的数量，并在数量相等时更新结果。对于给定的数据范围（字符串长度最大为10000），这个算法足够高效。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入字符串
s = input()

# 计算最大分割数
def calc_max_part(txt):
    """计算可以分割出的最大均衡子串数量"""
    x_cnt = 0  # X的计数
    y_cnt = 0  # Y的计数
    res = 0    # 结果计数
    
    # 遍历字符串中的每个字符
    for c in txt:
        # 统计X和Y的数量
        if c == 'X':
            x_cnt += 1
        else:
            y_cnt += 1