(C卷,100分)- 分割均衡字符串（Java & JS & Python & C）

题目描述

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

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

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

输入描述

输入一个均衡串。

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

输出描述

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

备注

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

用例

题目解析

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

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

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

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

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const s = await readline();

  let countX = 0;
  let countY = 0;

  let ans = 0;

  for (let c of s) {
    if (c == "X") {
      countX++;
    } else {
      countY++;
    }

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

  console.log(ans);
})();

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String s = sc.nextLine();

    int countX = 0;
    int countY = 0;

    int ans = 0;

    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == 'X') {
        countX++;
      } else {
        countY++;
      }

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

    System.out.println(ans);
  }
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    countX = 0
    countY = 0

    ans = 0

    for c in s:
        if c == 'X':
            countX += 1
        else:
            countY += 1

        if countX == countY:
            ans += 1

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

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

    int countX = 0;
    int countY = 0;

    int ans = 0;

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

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

        i++;
    }

    printf("%dn", ans);

    return 0;
}