📝 题目大意

判断一个仅由 A、B、C 组成的字符串是否为"扩展 ABC 字符串"，即能否表示为若干 A + 若干 B + 若干 C 按顺序拼接的形式（每部分可以为空）。换句话说，判断字符串是否匹配正则 A*B*C*。

💡 解题思路

1. 题目分析：$|S| \leq 100$，数据范围极小，可以直接模拟。核心约束是：字符串中所有 A 必须出现在 B 之前，所有 B 必须出现在 C 之前。一旦出现字符顺序"回退"（如 B 后面出现 A，或 C 后面出现 A / B），答案即为 No。

2. 算法推导：使用状态机思想，维护一个 state 变量表示当前所处的阶段：

   • state = 0：初始状态，尚未读入任何字符。
   • state = 1：已进入 A 阶段（见过 A，未见过 B 或 C）。
   • state = 2：已进入 B 阶段（见过 B，未见过 C）。
   • state = 3：已进入 C 阶段（见过 C）。

   遍历字符串中的每个字符 c：

   • 若 c == 'A'：如果 state > 1（说明已经出现过 B 或 C），则 A 出现在不允许的位置，标记非法并退出；否则将 state 置为 1。
   • 若 c == 'B'：如果 state > 2（说明已经出现过 C），则 B 出现在不允许的位置，标记非法并退出；否则将 state 置为 2（从 0 或 1 过渡到 B 阶段）。
   • 若 c == 'C'：将 state 置为 3（C 永远不会导致非法，因为它是最后一个阶段）。

3. 边界与细节：

   • 空字符串合法（题目明确说明），但本题 $|S| \geq 1$，无需处理。
   • 全 A、全 B、全 C 均合法（对应另外两个部分为空串的情况）。
   • 字符串 AB、BC、ABC 等合法；BA、CB、CA、ACB 等非法。
   • 注意 state 初始值为 0，当读到 A 时 state 变为 1，读到 B 时 state 变为 2——即使之前没有 A（即 state 从 0 直接跳到 2），这对应 $S_A$ 为空串的情况，是合法的。

⏱️ 复杂度分析

• 时间复杂度：$O(|S|)$，只需遍历字符串一次。
• 空间复杂度：$O(1)$，仅使用常数个变量。

💻 标准代码 (C++)

#include <iostream>
#include <string>
using namespace std;
int main() {
    string S;
    cin >> S;
    int state = 0;   // 状态机：0=初始, 1=A阶段, 2=B阶段, 3=C阶段
    bool ok = true;
    for (char c : S) {
        if (c == 'A') {
            if (state > 1) {  // 已出现过 B 或 C，A 不能再出现
                ok = false;
                break;
            }
            state = 1;        // 进入 A 阶段
        } else if (c == 'B') {
            if (state > 2) {  // 已出现过 C，B 不能再出现
                ok = false;
                break;
            }
            if (state < 2) state = 2;  // 进入 B 阶段（允许从 A 阶段或初始状态进入）
        } else if (c == 'C') {
            if (state < 3) state = 3;  // 进入 C 阶段（C 不会导致非法）
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}