一、问题描述
题目描述
均衡串定义:字符串中只包含两种字符,且这两种字符的个数相同。
给定一个均衡字符串,请给出可分割成新的均衡子串的最大个数。
约定:字符串中只包含大写的 X
和 Y
两种字符。
输入描述
输入一个均衡串。
字符串的长度:[2, 10000]。
给定的字符串均为均衡字符串
输出描述
输出可分割成新的均衡子串的最大个数。
备注
分割后的子串,是原字符串的连续子串
用例
用例 1
输入:
XXYYXY
输出:
2
说明:
XXYYXY
可分割为 2 个均衡子串,分别为:XXYY
、XY
题目解析
本题要求分割出最多的均衡子串,含义其实是分割出来的均衡子串无法再分解。
例如,用例 “XXYYXY” 分解出来的两个子串 “XXYY” 和 “XY” 都是无法再次分解出均衡子串的。
如果我们从一个均衡串中取走一个均衡子串,则均衡串剩余部分依旧是一个均衡串,因为取走的均衡子串中 X
和 Y
的数量是相等的,因此均衡串剩余部分的 X
和 Y
数量也一定是相等的,满足均衡串要求。
因此,本题我们只需要从左往右扫描输入的均衡串每个字符即可,统计扫描过程中,X
字符和 Y
字符的数量,每当两种字符数量相等时,则说明遇到了一个不可分解的均衡子串。
详细步骤
-
初始化计数器:
- 使用两个计数器
countX
和countY
分别记录X
和Y
的数量。 - 使用一个计数器
result
记录不可分解的均衡子串的数量。
- 使用两个计数器
-
扫描字符串:
- 从左往右遍历输入的均衡串。
- 对于每个字符,如果是
X
,则countX
加 1;如果是Y
,则countY
加 1。
-
检查均衡条件:
- 每次更新计数器后,检查
countX
和countY
是否相等。 - 如果相等,则说明遇到了一个不可分解的均衡子串,
result
加 1,并重置countX
和countY
为 0,继续扫描剩余部分。
- 每次更新计数器后,检查
-
输出结果:
- 遍历结束后,输出
result
,即不可分解的均衡子串的数量。
- 遍历结束后,输出
用例解释
用例 1
- 输入:
XXYYXY
- 输出:
2
解释:
- 遍历字符串
XXYYXY
:X
->countX = 1
X
->countX = 2
Y
->countY = 1
Y
->countY = 2
,此时countX == countY
,遇到一个均衡子串XXYY
,result = 1
,重置countX = 0
,countY = 0
X
->countX = 1
Y
->countY = 1
,此时countX == countY
,遇到一个均衡子串XY
,result = 2
,重置countX = 0
,countY = 0
- 最终结果为
2
。
通过上述步骤,我们可以高效地求出可分割成新的均衡子串的最大个数。这种方法的时间复杂度为 O(n)
,其中 n
是字符串的长度。
二、JavaScript算法源码
以下是 JavaScript 代码 的详细中文注释和逻辑讲解:
JavaScript 代码
// 引入 readline 模块,用于从控制台读取输入
const rl = require("readline").createInterface({ input: process.stdin });// 获取异步迭代器
var iter = rl[Symbol.asyncIterator]();// 定义异步函数 readline,用于读取一行输入
const readline = async () => (await iter.next()).value;// 立即执行异步函数
void (async function () {const s = await readline(); // 从控制台读取输入字符串 slet countX = 0; // 统计字符 'X' 的数量let countY = 0; // 统计字符 'Y' 的数量let ans = 0; // 记录满足条件的子串数量// 遍历字符串 s 中的每个字符for (let c of s) {if (c == "X") {countX++; // 如果字符是 'X',增加 countX} else {countY++; // 如果字符是 'Y',增加 countY}// 如果当前 'X' 和 'Y' 的数量相等,说明找到一个满足条件的子串if (countX == countY) {ans++; // 增加结果计数}}console.log(ans); // 输出结果
})();
代码逻辑讲解
1. 输入处理
- 使用
readline
模块从控制台读取输入字符串s
。 readline
是一个异步函数,通过await
等待输入完成。
2. 统计字符数量
- 定义两个变量:
countX
:统计字符'X'
的数量。countY
:统计字符'Y'
的数量。
- 遍历字符串
s
中的每个字符:- 如果字符是
'X'
,增加countX
。 - 如果字符是
'Y'
,增加countY
。
- 如果字符是
3. 判断满足条件的子串
- 在遍历过程中,每当
countX
和countY
相等时:- 说明从字符串开头到当前位置的子串中,
'X'
和'Y'
的数量相等。 - 增加结果计数
ans
。
- 说明从字符串开头到当前位置的子串中,
4. 输出结果
- 遍历结束后,输出满足条件的子串数量
ans
。
示例验证
示例 1:s = “XY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。
- 字符
- 结果:
ans = 1
(子串"XY"
满足条件)。
示例 2:s = “XXYY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'X'
:countX = 2
,countY = 0
。 - 字符
'Y'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 1
(子串"XXYY"
满足条件)。
示例 3:s = “XYXY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。 - 字符
'X'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 2
(子串"XY"
和"XYXY"
满足条件)。
总结
- 功能:统计字符串
s
中满足'X'
和'Y'
数量相等的子串数量。 - 核心逻辑:
- 遍历字符串,统计
'X'
和'Y'
的数量。 - 每当
'X'
和'Y'
的数量相等时,增加结果计数。
- 遍历字符串,统计
- 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
- 注意事项:
- 输入字符串只能包含
'X'
和'Y'
。 - 如果字符串为空,结果为
0
。
- 输入字符串只能包含
如果有其他问题,欢迎随时提问!
三、Java算法源码
以下是 Java 代码 的详细中文注释和逻辑讲解:
Java 代码
import java.util.Scanner; // 引入 Scanner 类,用于从控制台读取输入public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建 Scanner 对象,用于读取输入String s = sc.nextLine(); // 从控制台读取一行输入,存储到字符串 s 中int countX = 0; // 统计字符 'X' 的数量int countY = 0; // 统计字符 'Y' 的数量int ans = 0; // 记录满足条件的子串数量// 遍历字符串 s 中的每个字符for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == 'X') {countX++; // 如果当前字符是 'X',增加 countX} else {countY++; // 如果当前字符是 'Y',增加 countY}// 如果当前 'X' 和 'Y' 的数量相等,说明找到一个满足条件的子串if (countX == countY) {ans++; // 增加结果计数}}System.out.println(ans); // 输出结果}
}
代码逻辑讲解
1. 输入处理
- 使用
Scanner
类从控制台读取输入字符串s
。 sc.nextLine()
用于读取一行输入,并将其存储到字符串s
中。
2. 统计字符数量
- 定义两个变量:
countX
:统计字符'X'
的数量。countY
:统计字符'Y'
的数量。
- 遍历字符串
s
中的每个字符:- 使用
s.charAt(i)
获取当前字符。 - 如果字符是
'X'
,增加countX
。 - 如果字符是
'Y'
,增加countY
。
- 使用
3. 判断满足条件的子串
- 在遍历过程中,每当
countX
和countY
相等时:- 说明从字符串开头到当前位置的子串中,
'X'
和'Y'
的数量相等。 - 增加结果计数
ans
。
- 说明从字符串开头到当前位置的子串中,
4. 输出结果
- 遍历结束后,输出满足条件的子串数量
ans
。
示例验证
示例 1:s = “XY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。
- 字符
- 结果:
ans = 1
(子串"XY"
满足条件)。
示例 2:s = “XXYY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'X'
:countX = 2
,countY = 0
。 - 字符
'Y'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 1
(子串"XXYY"
满足条件)。
示例 3:s = “XYXY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。 - 字符
'X'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 2
(子串"XY"
和"XYXY"
满足条件)。
总结
- 功能:统计字符串
s
中满足'X'
和'Y'
数量相等的子串数量。 - 核心逻辑:
- 遍历字符串,统计
'X'
和'Y'
的数量。 - 每当
'X'
和'Y'
的数量相等时,增加结果计数。
- 遍历字符串,统计
- 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
- 注意事项:
- 输入字符串只能包含
'X'
和'Y'
。 - 如果字符串为空,结果为
0
。
- 输入字符串只能包含
如果有其他问题,欢迎随时提问!
四、Python算法源码
以下是 Python 代码 的详细中文注释和逻辑讲解:
Python 代码
# 输入获取
s = input() # 从控制台读取一行输入,存储到字符串 s 中# 算法入口
def getResult():countX = 0 # 统计字符 'X' 的数量countY = 0 # 统计字符 'Y' 的数量ans = 0 # 记录满足条件的子串数量# 遍历字符串 s 中的每个字符for c in s:if c == 'X':countX += 1 # 如果当前字符是 'X',增加 countXelse:countY += 1 # 如果当前字符是 'Y',增加 countY# 如果当前 'X' 和 'Y' 的数量相等,说明找到一个满足条件的子串if countX == countY:ans += 1 # 增加结果计数return ans # 返回满足条件的子串数量# 算法调用
print(getResult()) # 输出结果
代码逻辑讲解
1. 输入处理
- 使用
input()
函数从控制台读取一行输入,并将其存储到字符串s
中。
2. 统计字符数量
- 定义两个变量:
countX
:统计字符'X'
的数量。countY
:统计字符'Y'
的数量。
- 遍历字符串
s
中的每个字符:- 如果字符是
'X'
,增加countX
。 - 如果字符是
'Y'
,增加countY
。
- 如果字符是
3. 判断满足条件的子串
- 在遍历过程中,每当
countX
和countY
相等时:- 说明从字符串开头到当前位置的子串中,
'X'
和'Y'
的数量相等。 - 增加结果计数
ans
。
- 说明从字符串开头到当前位置的子串中,
4. 输出结果
- 调用
getResult()
函数,计算满足条件的子串数量。 - 使用
print()
函数输出结果。
示例验证
示例 1:s = “XY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。
- 字符
- 结果:
ans = 1
(子串"XY"
满足条件)。
示例 2:s = “XXYY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'X'
:countX = 2
,countY = 0
。 - 字符
'Y'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 1
(子串"XXYY"
满足条件)。
示例 3:s = “XYXY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。 - 字符
'X'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 2
(子串"XY"
和"XYXY"
满足条件)。
总结
- 功能:统计字符串
s
中满足'X'
和'Y'
数量相等的子串数量。 - 核心逻辑:
- 遍历字符串,统计
'X'
和'Y'
的数量。 - 每当
'X'
和'Y'
的数量相等时,增加结果计数。
- 遍历字符串,统计
- 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
- 注意事项:
- 输入字符串只能包含
'X'
和'Y'
。 - 如果字符串为空,结果为
0
。
- 输入字符串只能包含
如果有其他问题,欢迎随时提问!
五、C/C++算法源码:
以下是 C 代码 的详细中文注释和逻辑讲解:
C 代码
#include <stdio.h> // 引入标准输入输出库int main() {char s[10001]; // 定义一个字符数组 s,用于存储输入的字符串scanf("%s", s); // 从控制台读取字符串,存储到数组 s 中int countX = 0; // 统计字符 'X' 的数量int countY = 0; // 统计字符 'Y' 的数量int ans = 0; // 记录满足条件的子串数量int i = 0; // 定义索引变量 i,用于遍历字符串while (s[i] != '\0') { // 遍历字符串,直到遇到字符串结束符 '\0'if (s[i] == 'X') {countX++; // 如果当前字符是 'X',增加 countX} else {countY++; // 如果当前字符是 'Y',增加 countY}if (countX == countY) {ans++; // 如果当前 'X' 和 'Y' 的数量相等,增加结果计数}i++; // 移动到下一个字符}printf("%d\n", ans); // 输出结果return 0; // 程序正常结束
}
代码逻辑讲解
1. 输入处理
- 定义一个字符数组
s
,用于存储输入的字符串。 - 使用
scanf("%s", s)
从控制台读取字符串,并将其存储到数组s
中。
2. 统计字符数量
- 定义两个变量:
countX
:统计字符'X'
的数量。countY
:统计字符'Y'
的数量。
- 使用
while
循环遍历字符串s
中的每个字符:- 使用
s[i]
获取当前字符。 - 如果字符是
'X'
,增加countX
。 - 如果字符是
'Y'
,增加countY
。
- 使用
3. 判断满足条件的子串
- 在遍历过程中,每当
countX
和countY
相等时:- 说明从字符串开头到当前位置的子串中,
'X'
和'Y'
的数量相等。 - 增加结果计数
ans
。
- 说明从字符串开头到当前位置的子串中,
4. 输出结果
- 使用
printf("%d\n", ans)
输出满足条件的子串数量。
示例验证
示例 1:s = “XY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。
- 字符
- 结果:
ans = 1
(子串"XY"
满足条件)。
示例 2:s = “XXYY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'X'
:countX = 2
,countY = 0
。 - 字符
'Y'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 1
(子串"XXYY"
满足条件)。
示例 3:s = “XYXY”
- 遍历过程:
- 字符
'X'
:countX = 1
,countY = 0
。 - 字符
'Y'
:countX = 1
,countY = 1
。 - 字符
'X'
:countX = 2
,countY = 1
。 - 字符
'Y'
:countX = 2
,countY = 2
。
- 字符
- 结果:
ans = 2
(子串"XY"
和"XYXY"
满足条件)。
总结
- 功能:统计字符串
s
中满足'X'
和'Y'
数量相等的子串数量。 - 核心逻辑:
- 遍历字符串,统计
'X'
和'Y'
的数量。 - 每当
'X'
和'Y'
的数量相等时,增加结果计数。
- 遍历字符串,统计
- 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
- 注意事项:
- 输入字符串只能包含
'X'
和'Y'
。 - 如果字符串为空,结果为
0
。
- 输入字符串只能包含
如果有其他问题,欢迎随时提问!