返回目录

题目描述

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

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

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

输入描述

输入一个均衡串。

  • 字符串的长度：[2， 10000]。
  • 给定的字符串均为均衡字符串

输出描述

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

备注

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

示例：

输入XXYYXY
输出2
说明XXYYXY可分割为2个均衡子串，分别为：XXYY、XY
输入RLLLLRRRLR
输出3
说明可以分割为RL、LLLRRR、LR

题目解析

本题要求分割出最多的均衡子串，含义其实是分割出来的均衡子串无法再分解。

比如用例 "XXYYXY" 分解出来的两个子串 "XXYY" 和 "XY" 都是无法再次分解出均衡子串的。

如果我们从一个均衡串中取走一个的均衡子串，则均衡串剩余部分依旧是一个均衡串，因为取走的均衡子串中X和Y的数量是相等，因此均衡串剩余部分的X和Y数量也一定是相等的，满足均衡串要求。

因此，本题我们只需要从左往右扫描输入的均衡串每个字符即可，统计扫描过程中，X字符和Y字符的数量，每当两种字符数量相等时，则说明遇到了一个不可分解的均衡子串。

Python算法源码

# 接收用户输入的字符串
s = input()

# 初始化计数器和答案
countX = 0
countY = 0
ans = 0

# 遍历输入字符串的每个字符
for char in s:
    if char == 'X':
        countX += 1
    else:
        countY += 1

    # 如果'X'和'Y'的数量相等，答案加一
    if countX == countY:
        ans += 1

# 输出答案
print(ans)

C算法源码


#include <stdio.h>

int main() {
    char s[1000];
    scanf("%s", s);

    int countX = 0;
    int countY = 0;

    int ans = 0;

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == 'X') {
            countX++;
        } else {
            countY++;
        }

        if (countX == countY) {
            ans++;
        }
    }

    printf("%d\n", ans);

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象来读取标准输入
        Scanner sc = new Scanner(System.in);
      
        // 读取一行输入作为字符串s
        String s = sc.nextLine();
      
        // 初始化计数变量和答案变量
        int countX = 0;
        int countY = 0;
        int ans = 0;
      
        // 初始化索引变量
        int i = 0;
        // 使用while循环遍历字符串直到末尾
        while (i < s.length()) {
            // 如果当前字符是'X'，增加X的计数
            if (s.charAt(i) == 'X') {
                countX++;
            } else {
                // 否则，假定只有'Y'，增加Y的计数
                countY++;
            }
          
            // 如果X和Y的计数相等，增加答案变量
            if (countX == countY) {
                ans++;
            }
          
            // 移动到下一个字符
            i++;
        }
      
        // 输出最终的答案
        System.out.println(ans);
    }
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏