《蓝桥杯每日一题》双指针·AcWing 3768. 字符串删减

用户10604450

发布于 2024-03-15 14:02:10

3280

文章被收录于专栏：练习两年半练习两年半

1.题目

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

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

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

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

3≤n≤100

样例

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

2.题目分析

题目要求的就是给定字符串ss中连续出现′x′的子串。

对于每一个长度len>=3 的x子串, 更新ans+=len−2。

于是我们可以枚举这样的x子串。注意到如果我们统计过(l,r)的x子串，那么我们无需也不能再统计(l,r−1)的x子串，当然也不会再统计(l+1,r−1)的子串。于是双指针性质成立，r指针始终不会减少。由此得到时间复杂度O(n))的做法。

3.Ac代码

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int res=0;
        for(int l=1,r=1;l<=n;l++){
            r=l;  //右边界从左边界开始，并不断右移
            //减 1是因为字符下标从0开始，双指针从1开始
            while (r<=n && s.charAt(r-1)=='x')  r++;
            int len=r-l; //字符串长度
            if(len>=3) res+=len-2;
            l=r; //查询完一次连续的，更新左边界到最右边
        }
        System.out.println(res);
    }
}