官方题解｜aaaccgo

题目解析

本题考察字符串和循环结构。

我们有很多种方法来解决这道题目。

这里采用一种比较方便的做法：

首先使用以下方法将字符串 $S$ 「去重」：

1. 从第二个字符开始遍历字符串 $S$；
2. 若当前字符和前一个保留的字符不相同，则保留该字符；
3. 若当前字符和前一个保留的字符相同，则不保留该字符。

去重后的字符串一定为 $\tt{"acgo"}$，否则说明不能够按照题目要求进行拆分。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string s; cin >> s;
    int j = 0, n = s.size();
    for (int i = 1; i < n; ++i)
        if (s[i] != s[j]) s[++j] = s[i];
    cout << (s.substr(0, j+1) == "acgo" ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

将字符串去重时间复杂度 $\mathrm{O}(N)$。