【双指针】字符串删减

题目

3768. 字符串删减 - AcWing题库

---

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

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

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

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

输入格式

第一行包含整数 $n$ 。

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

输出格式

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

数据范围

$3 \le n \le 100$

输入样例1：

6
xxxiii

输出样例1：

1

输入样例2：

5
xxoxx

输出样例2：

0

输入样例3：

10
xxxxxxxxxx

输出样例3：

8

解题

方法一：双指针 滑动窗口

思路

双指针思想，维护一个长度为 $3$ 的滑动窗口中 'x' 的数量，如果大于等于 $3$ 则增加计数。

代码

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);
    }
}