文章目录

• 一、题目
• • 1、原题链接
  • 2、题目描述
• 二、解题报告
• • 1、思路分析
  • 2、时间复杂度
  • 3、代码详解
• 三、知识风暴
• • 双指针

一、题目

1、原题链接

3768. 字符串删减

2、题目描述

给定一个由 n 个小写字母构成的字符串。

现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。

请问，最少需要删掉多少个字母？

如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。

输入格式

第一行包含整数 n。

第二行包含一个长度为 n 的由小写字母构成的字符串。

输出格式

输出最少需要删掉的字母个数。

数据范围

3≤n≤100

输入样例1：

6
xxxiii

输出样例1：

1

输入样例2：

5
xxoxx

输出样例2：

0

输入样例3：

10
xxxxxxxxxx

输出样例3：

8

二、解题报告

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 
#include 
using namespace std;
int n,ans;
string s;
int main(){cin>>n;cin>>s;for(int i=0;i   //从前到后依次枚举长度为3的子串的起点if(s.substr(i,3)=="xxx"){    //每出现连续3个x说明需要删一个，ans++ans++;}}cout<

#include 
#include 
#include 
using namespace std;
int n,ans;
string s;
int main(){cin>>n;cin>>s;for(int i=0;i    //从前往后枚举字符串s的每个位置if(s[i]=='x'){              //如果当前位置为xint j=i+1;              //j指向当前位置的下一位         while(j