1.题目
给定一个由 n 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。
请问，最少需要删掉多少个字母？
如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤100
样例
输入样例16xxxiii输出样例11输入样例25xxoxx输出样例20输入样例310xxxxxxxxxx输出样例38
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); } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
