A23494. ABC字符串小Y给了小X一个长度为n的只包含大写字母A,B,C的字符串。你可以对这个字符串进行如下操作：将子串ABC变成BCA。小X想知道这个字符串最多能进行多少次操作。一个字符串的子串是把这个字符串通过删去头部和尾部若干个字符形成的字符串。例如：A, B, BB, AB, ABB 是 ABB 的子串，ABA 不是 ABBA 的子串。输入一行一个长度为n的字符串S。输出一行一个整数表示答案。样例…
填空题
较易
知识点
题目描述
ABC字符串
小Y给了小X一个长度为n的只包含大写字母A,B,C的字符串。你可以对这个字符串进行如下操作：将子串ABC变成BCA。
小X想知道这个字符串最多能进行多少次操作。
一个字符串的子串是把这个字符串通过删去头部和尾部若干个字符形成的字符串。
例如：A, B, BB, AB, ABB 是 ABB 的子串，ABA 不是 ABBA 的子串。
输入
一行一个长度为n的字符串S。
输出
一行一个整数表示答案。
样例输入1
ABCABC样例输入2
ABCACCBABCBCCAACBC样例输出1
3样例输出2
6提示
样例解释1
ABCABC
ABCB CA
BCABCA
BCBCAA
最多操作3次。数据范围
对于全部测试点：n<=200000。
对于测试点1-4：n<=10
对于测试点5-7：n<=1000，并且保证无论按照什么顺序操作，被操作的子串两两不相交（换句话说，一个下标不会被两个被操作的字符串同时覆盖）
对于测试点8-10：n<=200000
参考答案
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
int count = 0;
int i = 0;
int n = s.size();
while (i <= n - 3) {
if (s.substr(i, 3) == "ABC") {
count++;
// 替换为BCA（即交换i和i+1位置的字符）
swap(s[i], s[i+1]);
// 回溯检查前面是否形成新的ABC
if (i > 0) i--;
else i++; // 无法回溯则前进
} else {
i++;
}
}
cout << count << endl;
return 0;
}
上一题
下一题