题目描述
给定一个由 n 个小写字母构成的字符串。
现在,需要删掉其中的一些字母,使得字符串中不存在连续三个或三个以上的 x。
请问,最少需要删掉多少个字母?
如果字符串本来就不存在连续的三个或三个以上 x,则无需删掉任何字母
输入格式
第一行包含整数 n
第二行包含一个长度为 n 的由小写字母构成的字符串
输出格式
输出最少需要删掉的字母个数
输入样例
6
xxxiii
输出样例
1
算法
双指针
我们每次只计算字母 ‘x’ 的次数,一旦大于 2,则移动后面的指针
如果前面的指针指向的数不是 ‘x’,则可以清空次数为 0
如果发现 ‘x’ 的次数等于 1,则让此时的 j 等于 i,实现 j 的更新
C++ 代码
#include <iostream>
using namespace std;
const int N = 30;
int a[N];
int main()
{
int n;
scanf("%d",&n);
string s;
cin>>s;
int count = 0;
int j=0;
int i = 0;
for(i=0;i<n;i++)
{
if(s[i]=='x')
{
a[ 'x' - 'a' ]++;
if(a['x' - 'a'] == 1) j = i;
}
else
{
a[ 'x' - 'a' ] = 0;
}
while(a[ s[j] - 'a' ] > 2)
{
a[ s[j] - 'a' ]--;
j++;
count ++;
}
}
printf("%d",count);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla