ZYF009 字符串删减
大约 3 分钟
ZYF009 字符串删减
【算法】 双指针、贪心
【C++】 字符串、计数
【难度】 入门
一、题目简述
给定一个长度为 的字符串 ,只包含小写字母。你需要从中删掉尽可能少的字母,使得修改后的字符串中不存在连续 3 个或以上的 x。求最少需要删除的字母数量。
例如:字符串 "xxxiii" 中,前三个 x 连续,需要至少删除 1 个 x,变为 "xxiii"(或者变成 "xxiii" 即删掉第 3 个 x)。最少删除 1 个。
二、解题思路
算法选择:贪心
这是一个非常简单的贪心问题。我们只需要关注连续 x 的个数。
遍历字符串,维护当前连续 x 的计数 :
- 遇到字符
x: 加 1。- 如果 ,说明出现了连续 3 个
x,我们需要删除当前这个x,计数器ans++,然后 减 1(因为删掉当前这个x后,连续数变为 2)。
- 如果 ,说明出现了连续 3 个
- 遇到非
x字符:连续中断, 重置为 0。
为什么这是最优的?
每当我们发现连续 x 的个数达到 3 个,必须删除至少其中一个。贪心选择删除当前这个(即第 3 个)是最优的,因为:
- 删掉当前这个,前面的 2 个
x保留,后面的x重新计数。 - 不管删除哪一个,连续 3 个
x都会被打断,删除次数相同。
因此每次遇到第 3 个连续 x 就删除它,可以保证删除次数最少。
手动模拟
以字符串 "xxxiii" 为例:
| 位置 | 字符 | cnt (之前) | 操作 | cnt (之后) | ans |
|---|---|---|---|---|---|
| 1 | x | 0 | cnt=1 | 1 | 0 |
| 2 | x | 1 | cnt=2 | 2 | 0 |
| 3 | x | 2 | cnt=3≥3, ans++, cnt-- | 2 | 1 |
| 4 | i | 2 | cnt=0 | 0 | 1 |
| 5 | i | 0 | cnt=0 | 0 | 1 |
| 6 | i | 0 | cnt=0 | 0 | 1 |
最少删除 1 个。
再以字符串 "xxxxxx" 为例(6 个连续 x):
| 位置 | cnt (之后) | 是否需要删除 | ans |
|---|---|---|---|
| 1 | 1 | — | 0 |
| 2 | 2 | — | 0 |
| 3 | 3→2 | 删第 3 个 | 1 |
| 4 | 3→2 | 删第 4 个 | 2 |
| 5 | 3→2 | 删第 5 个 | 3 |
| 6 | 3→2 | 删第 6 个 | 4 |
最终保留的是第 1、2 个 x,剩下的都被删了。共删除 4 个。
再以字符串 "xxixxx" 为例:
| 位置 | 字符 | cnt | ans | 说明 |
|---|---|---|---|---|
| 1 | x | 1 | 0 | — |
| 2 | x | 2 | 0 | — |
| 3 | i | 0 | 0 | 非 x,中断 |
| 4 | x | 1 | 0 | — |
| 5 | x | 2 | 0 | — |
| 6 | x | 3→2 | 1 | 删第 6 个 |
最少删除 1 个。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
int cnt = 0; // 当前连续 x 的个数
int ans = 0; // 最少删除次数
for (char c : s) {
if (c == 'x') {
cnt++;
if (cnt >= 3) {
ans++; // 删除当前这个 x
cnt--; // 删掉后连续数减 1
}
} else {
cnt = 0; // 遇到非 x,重新计数
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,只需遍历字符串一次。
- 空间复杂度:(不计输入字符串的存储),只用了几个计数变量。
知识扩展
这道题本质上是在维护一个长度为 2 的滑动窗口:任何时刻最多允许连续 2 个 x。每当窗口即将超过 2 时,就需要进行一次删除操作。
如果题目改成"不存在连续 个或以上的 x",只需要将判断条件 cnt >= 3 改成 cnt >= k 即可。
易错点
- 不要忘记在删除当前
x后执行cnt--。比如"xxxx",处理完第 3 个后 ,这样第 4 个才能正确触发第 3→2 的计数逻辑。 - 注意是连续
x的计数,遇到其他字符时 要清零。
