官方题解｜替换子串使两串相等

题目解析

两种操作本质上就是可以把 $s$ 中的 'a' 向右移动，'c' 向左移动。

所以把 $s$ 和 $t$ 中的所有字符 'b' 去掉之后，两个字符串应该是相同的。

另外，由于 'a' 不能向左移动，'c' 不能向右移动，所以要检查字符串 $s$ 和 $t$ 中，对应的字符 'a' 和字符 'b' 的下标。

对于字符 'a'，在 $s$ 中每个字符 'a' 在字符串 $t$ 中都应该 有一个下标大于等于 它的 'a' 与之对应；
相对对应的，在 $s$ 中每个字符 'c' 在字符串 $t$ 中都应该 有一个下标小于等于 它的 'c' 与之对应。

AC代码

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        string s, t;
        cin >> s >> t;
        string a, b;
        for (auto &x : s)
            if (x != 'b') a.push_back(x);
        for (auto &x : t)
            if (x != 'b') b.push_back(x);
        if (a != b) {
            cout << "NO" << '\n';
            continue;
        }
        auto check = [&]() {
            vector<int> idx;
            for (int i = 0; i < n; ++i)
                if (s[i] != 'b') idx.push_back(i);
            for (int i = 0, j = 0; i < n; ++i) {
                if (t[i] == 'b') continue;
                if (t[i] == 'a' and i < idx[j]) return false;
                if (t[i] == 'c' and i > idx[j]) return false;
                ++j;
            }
            return true;
        };
        cout << (check() ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析

检查 $s$ 和 $t$ 去掉所有字符 'b' 之后是否相等时间复杂度为 $O(n)$。
检查 $s$ 中字符 'a' 和 'b' 相对于在字符串 $t$ 中的位置时间复杂度为 $O(n)$。

---