刷题笔记合集🔗

问题描述

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

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

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

输入格式

输入一个均衡串。

• 字符串的长度:[2,10000]
• 给定的字符串均为均衡字符串

输出格式

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

备注

分割后的子串,是原字符串的连续子串。

样例1

输入:

XXYYXY

输出:

2

说明:

• XXYYXY可分割为2个均衡子串
• 分别为:XXYY、XY

题解

本题可以使用贪心法解决:

1. 从左到右扫描字符串
2. 统计X和Y的数量
3. 当X和Y数量相等时,找到一个均衡子串
4. 继续扫描剩余部分

时间复杂度:O(n),其中n为字符串长度。

参考代码

# 读取输入
s = input()

def getResult():
    x_count = 0  # X的数量
    y_count = 0  # Y的数量
    ans = 0      # 均衡子串数量
    
    for c in s:
        if c == 'X':
            x_count += 1
        else:
            y_count += 1
            
        if x_count == y_count:
            ans += 1
            
    return ans

print(getResult())

import java.util.Scanner;

public class Main {
    public static void main(String[] arg