题目描述

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

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

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

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

输入格式
第一行包含整数 n。

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

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

数据范围
3≤n≤100

样例

输入样例1：
6
xxxiii
输出样例1：
1
输入样例2：
5
xxoxx
输出样例2：
0
输入样例3：
10
xxxxxxxxxx
输出样例3：
8

双指针

$O(n)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int l=0,r=0;
    int ans=0;
    while(l<s.size()){
        if (s[l]!='x') {
            ++l;
            continue;
        }
        r=l;
        while(r+1<s.size() && s[r+1]=='x') ++r;
        ans+=r-l+1>=3? r-l-1:0;
        l=r+1;
    }
    cout<<ans<<endl;
}