【贪心】2023C-分割均衡字符串

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3103

题目描述

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

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

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

输入描述

均衡串: XXYYXY

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

输出描述

输出一个数字，表述可分割成新的均衡子串的最大个数。

如上述例子可分割为两个子串，XXYY和XY，输出答案为2。

补充说明

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

示例

输入

XXYYXY

输出

解题思路

注意，本题和LeetCode1221、分割平衡字符串完全相同。

对于均衡字符串，以下结论非常重要：若将某个已知的均衡字符串s分割为A和B两个子串，且A为均衡字符串，则B一定也为均衡字符串。

因此，对于任意的均衡字符串s，如果它能够被切割成若干个均衡字符串，为了使得最终的均衡子串尽可能多，我们一定会贪心地对它进行切割直到无法再切割为止。

因此只需要一次遍历原字符串s，并同时记录遍历过程中X的个数X_num和Y的个数Y_num，一旦发现X_num == Y_num，则找到了一个子串，立马进行切割。核心代码为

for ch in s:
    if ch == "X":
        X_num += 1
    else:
        Y_num += 1
    if X_num == Y_num:
        ans += 1

本题更加严谨的证明可以使用数学归纳法完成，感兴趣的同学可以自行进行证明。

代码

Python

# 题目：【贪心】2023C-分割均衡字符串
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心，
# 代码看不懂的地方，请直接在群上提问


s = input()
# 初始化答案变量
ans = 0
# 初始化记录遍历过程中X个数和Y个数的变量
X_num, Y_num = 0, 0
# 从头到尾一次遍历字符串s
for ch in s:
    # 如果ch为X，更新X_num
    if ch == "X":
        X_num += 1
    # 如果ch为Y，更新Y_num
    else:
        Y_num += 1
    # 贪心地进行切割：
    # 一旦发现X_num等于Y_num，进行切割
    # 均衡子串数目+1
    if X_num == Y_num:
        ans += 1

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int ans = 0, X_num = 0, Y_num = 0;

        for (char ch : s.toCharArray()) {
            if (ch == 'X') {
                X_num++;
            } else {
                Y_num++;
            }
            if (X_num == Y_num) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = 0, X_num = 0, Y_num = 0;

    for (char ch : s) {
        if (ch == 'X') {
            X_num++;
        } else {
            Y_num++;
        }
        if (X_num == Y_num) {
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历原字符串

空间复杂度：O(1)。仅需若干常数变量