一、题目
1、原题链接
3768. 字符串删减
2、题目描述
给定一个由 n 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。
请问，最少需要删掉多少个字母？
如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤100
输入样例1：
6
xxxiii
1
2
输出样例1：
1
1
输入样例2：
5
xxoxx
1
2
输出样例2：
0
1
输入样例3：
10
xxxxxxxxxx
1
2
输出样例3：
8
1
二、解题报告
1、思路分析
我的思路：
（1）遍历一遍字符串，求出从每个位置开始，长度为3的子串，如果该子串中包含三个x，则需要删去一个。
（2）统计所有位置的需要删除的个数，输出即可。
思路来源：y总蓝桥杯每日一题b站视频链接
y总yyds
y总思路：
（1）利用双指针算法找出每段连续x的个数，如连续的x的个数小于3，则不需要删除；否则如果连续x的个数大于等于3个，则需要删除x，并使得该段x的个数等于2个。
（2）统计所有需要删除的x的个数，输出即可。
2、时间复杂度
我的思路时间复杂度O(n)
y总思路时间复杂度O(n)
3、代码详解
我的思路代码
#include <iostream>
#include <string>
using namespace std;
int n,ans;
string s;
int main(){
cin>>n;
cin>>s;
for(int i=0;i<s.size()-2;i++){ //从前到后依次枚举长度为3的子串的起点
if(s.substr(i,3)=="xxx"){ //每出现连续3个x说明需要删一个，ans++
ans++;
}
}
cout<<ans;
return 0;
}
y总思路代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n,ans;
string s;
int main(){
cin>>n;
cin>>s;
for(int i=0;i<s.size();i++){ //从前往后枚举字符串s的每个位置
if(s[i]=='x'){ //如果当前位置为x
int j=i+1; //j指向当前位置的下一位
while(j<n&&s[j]=='x') j++; //如果j也是x，j++，最终j指向该段连续的x的下一个位置
ans+=max(j-i-2,0); //j-i为该段连续x中x的数量，j-i-2是需要删除x的数量，有可能连续x的个数小于3，所以需要与0取max
i=j-1; //i指向当前连续一段x的最后一位的x的位置，下次循环前i++，就指向了该段连续x之后的第一个不是x的位置
}
}
cout<<ans;
return 0;
}
三、知识风暴
双指针
如果在暴力求解过程中出现需要用双层循环来遍历，而且两层循环的变量走向具有单调性，则可以进行双指针优化，可以将时间复杂度降低至O(n)。
