好字符串 - 题解

标签与难度

标签: 字符串, 贪心, 思维题, 模拟, 入门

难度: 800

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道关于字符串的有趣问题，呐~

题目是这样子的：我们拿到一个由小写字母组成的字符串 $s$，它的长度是 $n$。我们可以对这个字符串进行最多一次操作。这个操作就是：从字符串里选一个字符，然后把它删掉。

我们的目标是，在进行最多一次删除操作后（也可以一次都不删哦），得到的新字符串 $s'$ 是不是一个“好字符串”。

那么，什么是“好字符串”呢？就是一个字符串里，任何两个相邻的字符都不能相同。比如说，"abac"是好字符串，但"aabc"就不是，因为它有"aa"这对坏邻居，喵~

如果通过操作可以得到一个好字符串，我们就输出 "YES"，否则就输出 "NO"。

解题思路分析

这道题看起来是要我们尝试删除每一个字符，然后检查剩下的字符串是不是“好”的。但那样也太麻烦了，对吧？本喵的胡须都感应到了，一定有更聪明的办法，喵！

让我们先来分析一下，一个字符串为什么会“不好”。原因很简单，就是因为它存在至少一对相邻且相同的字符，比如 s[i] == s[i-1]。我们就叫这种讨厌的邻居为“坏邻居对”吧！

我们的任务，就是要通过最多一次删除，消灭掉所有的“坏邻居对”。

我们来分情况讨论一下，根据原字符串中“坏邻居对”的数量，看看会发生什么，呐：

情况一：原字符串中有 0 个“坏邻居对”

如果一开始就没有“坏邻居对”，那这个字符串本身就是一个“好字符串”啦！我们不需要做任何操作（也就是删除0次），就已经满足条件了。所以，直接输出 "YES" 就好啦！ 例如："abcdefg"，完美~

情况二：原字符串中有 1 个“坏邻居对”

假设字符串是 "...abccde..."，这里只有一对坏邻居 cc。我们有一次宝贵的删除机会，要怎么用呢？当然是用来拆散这对坏邻居啦！ 我们可以删除第一个 c，字符串变成 "...abcde..."。哇，所有的坏邻居都不见了！ 或者删除第二个 c，结果也是一样的。 因为原来只有这一处问题，我们用一次删除把它修正了，其他地方本来就是好的，所以整个字符串就变好了！ 所以，如果只有一个“坏邻居对”，答案是 "YES"，喵~

情况三：原字符串中有 2 个或更多“坏邻居对”

这下情况就变得棘手了呢。

• 如果这些“坏邻居对”是分开的，比如 "...aa...bb..."。我们只有一次删除机会。如果我们删掉一个 a 来修复 aa，那么 bb 还在那里捣乱。反过来，如果我们去修复 bb，aa 就会被留下。一次删除只能修复一个地方，顾此失彼，没办法把它们全部消灭掉。所以，这种情况下，答案是 "NO"。

• 如果这些“坏邻居对”是连在一起的，比如 aaa。这里其实有两对坏邻居：第1个和第2个a，第2个和第3个a。 如果我们删除中间的 a，字符串剩下 aa。唔，还是有一个“坏邻居对”。 如果我们删除两边的任意一个 a，字符串还是剩下 aa。 看来，即使坏邻居们挤在一起，一次删除也没办法把它们彻底清除干净。所以，答案还是 "NO"。

总结一下喵！

通过本喵细致的分析，我们发现了一个超级简单的规律！

• 如果原字符串中“坏邻居对”的数量是 0 或 1，我们总能通过最多一次删除（0次或1次）让它变成一个好字符串。
• 如果“坏邻居对”的数量大于等于 2，那么无论我们怎么删，都至少会留下一个“坏邻居对”。

所以，解题的关键就变成了——数一数原字符串里到底有多少对“坏邻居”！

我们的算法就是：

1. 遍历字符串。
2. 用一个计数器，记录下 s[i] == s[i-1] 的情况发生了多少次。
3. 最后，如果计数器的值小于等于 1，就输出 "YES"，否则输出 "NO"。

是不是超级简单呢？喵~

代码实现

下面就是本喵根据这个思路，精心为你准备的C++代码啦！注释写得很详细哦，希望能帮到你~

#include <iostream>
#include <string>
#include <vector>

// 一个好习惯是把解题逻辑放在一个函数里，喵~
void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 如果字符串长度为1，那它肯定是好字符串，没有相邻的字符嘛
    if (n <= 1) {
        std::cout << "YES" << std::endl;
        return;
    }

    // `bad_pairs_count` 用来统计 "坏邻居对" 的数量
    int bad_pairs_count = 0;

    // 我们从第二个字符开始遍历，这样才能和它前面的字符比较
    // 循环的索引 i 代表当前字符的位置，i-1 是它前一个字符的位置
    for (int i = 1; i < n; ++i) {
        // 如果当前字符和它前面的字符相同，就发现了一对坏邻居
        if (s[i] == s[i - 1]) {
            bad_pairs_count++;
        }
    }

    // 根据我们的分析，只要坏邻居对的数量不多于1个，我们就有办法搞定！
    if (bad_pairs_count <= 1) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
}

int main() {
    // 为了让输入输出更快一点，这是竞赛中的常用技巧哦
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    // 调用我们的解题函数
    solve();
    
    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$ 我们只需要从头到尾遍历一次字符串来计数，其中 $N$ 是字符串的长度。所以时间复杂度和字符串的长度是线性关系，非常高效！

• 空间复杂度: $O(1)$ 我们只用了一个额外的变量 bad_pairs_count 来计数，占用的空间是固定的，不会随着字符串长度 $N$ 的增加而增加。输入的字符串 s 占用的 $O(N)$ 空间通常不算在额外空间复杂度里。

知识点总结

这道题虽然简单，但也能学到东西哦！

1. 问题转化: 核心在于把一个看似复杂的操作问题（尝试删除每个位置）转化为一个简单的计数问题（数一数有多少个“坏邻居对”）。这是解决算法问题时非常重要的思维方式！
2. 分类讨论: 通过对“坏邻居对”数量的分类讨论（0个、1个、2个及以上），我们能清晰地推导出问题的解法。
3. 边界条件: 注意处理像字符串长度为1这样的边界情况，虽然在这个问题的逻辑下它被自然地包含了，但在其他问题中，想清楚边界总是好的。

希望这篇题解能让你有所收获，喵~ 如果还有其他问题，随时可以来找本喵哦！我们一起进步！