一、題目

1、原題鏈接

3768. 字符串刪減

2、題目描述

給定一個由 n 個小寫字母構成的字符串。

現(xiàn)在，需要刪掉其中的一些字母，使得字符串中不存在連續(xù)三個或三個以上的 x。

請問，最少需要刪掉多少個字母？

如果字符串本來就不存在連續(xù)的三個或三個以上 x，則無需刪掉任何字母。

輸入格式

第一行包含整數(shù) n。

第二行包含一個長度為 n 的由小寫字母構成的字符串。

輸出格式

輸出最少需要刪掉的字母個數(shù)。

數(shù)據(jù)范圍

3≤n≤100

輸入樣例1：

6
xxxiii

輸出樣例1：

1

輸入樣例2：

5
xxoxx

輸出樣例2：

0

輸入樣例3：

10
xxxxxxxxxx

輸出樣例3：

8

二、解題報告

1、思路分析

我的思路：
（1）遍歷一遍字符串，求出從每個位置開始，長度為3的子串，如果該子串中包含三個x，則需要刪去一個。
（2）統(tǒng)計所有位置的需要刪除的個數(shù)，輸出即可。

思路來源：y總藍橋杯每日一題b站視頻鏈接
y總yyds

y總思路：
（1）利用雙指針算法找出每段連續(xù)x的個數(shù)，如連續(xù)的x的個數(shù)小于3，則不需要刪除；否則如果連續(xù)x的個數(shù)大于等于3個，則需要刪除x，并使得該段x的個數(shù)等于2個。
（2）統(tǒng)計所有需要刪除的x的個數(shù)，輸出即可。

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"){    //每出現(xiàn)連續(xù)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'){              //如果當前位置為xint j=i+1;              //j指向當前位置的下一位         while(j<n&&s[j]=='x') j++;   //如果j也是x，j++，最終j指向該段連續(xù)的x的下一個位置ans+=max(j-i-2,0);         //j-i為該段連續(xù)x中x的數(shù)量，j-i-2是需要刪除x的數(shù)量，有可能連續(xù)x的個數(shù)小于3，所以需要與0取maxi=j-1;                   //i指向當前連續(xù)一段x的最后一位的x的位置，下次循環(huán)前i++，就指向了該段連續(xù)x之后的第一個不是x的位置}}cout<<ans;return 0;
}

三、知識風暴

雙指針

如果在暴力求解過程中出現(xiàn)需要用雙層循環(huán)來遍歷，而且兩層循環(huán)的變量走向具有單調性，則可以進行雙指針優(yōu)化，可以將時間復雜度降低至O(n)。