题目
给定一个由 个小写字母构成的字符串。
现在,需要删掉其中的一些字母,使得字符串中不存在连续三个或三个以上的 x
。
请问,最少需要删掉多少个字母?
如果字符串本来就不存在连续的三个或三个以上 x
,则无需删掉任何字母。
输入格式
第一行包含整数 。
第二行包含一个长度为 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
输入样例1:
6
xxxiii
输出样例1:
1
输入样例2:
5
xxoxx
输出样例2:
0
输入样例3:
10
xxxxxxxxxx
输出样例3:
8
解题
方法一:双指针 滑动窗口
思路
双指针思想,维护一个长度为 的滑动窗口中 'x'
的数量,如果大于等于 则增加计数。
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
char[] s = in.readLine().toCharArray();
int cnt = 0;
int l = 0, r = 0, ans = 0;
while (r < n) {
if (s[r++] == 'x') ++cnt;
if (r - l > 3) {
if (s[l++] == 'x') --cnt;
}
if (cnt >= 3) ++ans;
}
System.out.println(ans);
}
}
评论区