【深基6.习3】单词覆盖还原

解题思路

对每个可能的 boy 起点 i，若 s[i] 是 b、s[i+1] 是 o 或 s[i+2] 是 y，说明这里贴过 boy。同样用 g、i、r、l 对 girl 起点判断。

正确性说明

两单词内的字符均不重复且彼此不共用字母，因此任一残留字符都唯一确定所属单词的起点。题目保证每个贴词至少留一个字符，对每个起点以或条件计一次，恰好恢复全部词数。

易错点

同一次粘贴可能留多个字符，用逻辑或只算一次；遍历起点不能越界。

复杂度

时间 O(L)，空间 O(L)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int b = 0, g = 0;
    for (int i = 0; i + 2 < int(s.size()); i++)
        if (s[i] == 'b' || s[i + 1] == 'o' || s[i + 2] == 'y')
            b++;
    for (int i = 0; i + 3 < int(s.size()); i++)
        if (s[i] == 'g' || s[i + 1] == 'i' || s[i + 2] == 'r' || s[i + 3] == 'l')
            g++;
    cout << b << "\n" << g << "\n";
    return 0;
}