题目描述
给定一个由 $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
算法
(暴力枚举) $O(n^2)$
write here…
时间复杂度
write here…
空间复杂度
write here…
C++ 代码
#include "bits/stdc++.h"
using namespace std;
map<char, int> dd;
int n;
string s;
int main() {
cin >> n >> s;
s = "?" + s;
int cnt = 0;
for (int i = 3; i <= n; i++) {
if (s[i - 2] == 'x' && s[i - 1] == 'x' && s[i] == 'x') cnt++;
}
cout << cnt << '\n';
return 0;
}