题目描述

给定两个长度为 $n$ 的字符串 $s$ 和 $t$。 两个字符串中的每个字符都是a、b或c。

在一个操作中，你可以执行其中之一：

• 选择 $s$ 中出现的 ab 并将其替换为 ba ；
• 选择 $s$ 中出现的 bc 并将其替换为 cb。

如果可以执行任意多次移动（可能为零），你能否将字符串 $s$ 变为字符串 $t$？

输入格式

第一行一个整数 $q$ ( $1≤q≤10^4$ )，表示数据的组数。

对于每组测试用例，第一行一个整数 $n$ ( $1≤n≤10^5$ )，表示字符串 $s$ 和 $t$ 的长度。

第二行包含长度为 $n$ 的字符串 $s$。 每个字符是a、b或c。

第三行包含长度为 $n$ 的字符串 $t$。 每个字符是a、b或c。

所有测试用例的 $n$ 总和不超过 $10^5$。

输出格式

$q$ 行，每组测试用例一行，为 YES 或 NO，表示是否能将串 $s$ 变为串 $t$。

样例输入

5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab

样例输出

YES
NO
YES
YES
NO

思路

交换两个字符等价于固定一个字符移动另一个字符。由于两种移动操作中都有 “b”，不妨把它看成是固定的，则两种操作分别等价于：

• 将 “a” 通过 “b” 右移；

• 将 “c” 通过 “b” 左移。

可发现如下性质：

1. “a” 只能右移，”c” 只能左移。

2. 由于 “ac” 和 “ca” 都不能互换，因此 “a”、”c” 的相对位置不能发生改变。

因此，若 $s$ 能变成 $t$，则

1. 两个串中 “b” 的数量一定相等。

2. 删除所有 “b” 后，两个串应该相等。

3. $s$ 中第 $i$ 个 “a” 的下标应小于等于 $t$ 中第 $i$ 个 “a” 的下标。

4. $s$ 中第 $i$ 个 “c” 的下标应大于等于 $t$ 中第 $i$ 个 “c” 的下标。

证明：若上述条件成立，则 $s$ 一定能变成 $t$。

从前往后找到第一个不相等的字符 $s_i$ 和 $t_i$，此时需要移动 $s_i$，由于两个串的左边都相等，且剩余串仍然满足以上所有条件，只需考虑自此之后的递归子问题。由条件 $3$ 得 $t_i \ne a$：

1. 若 $t_i = b$。由条件 $4$，$s_i \ne c$。又 $s_i \ne t_i$，则 $s_i = a$。从 $s_i$ 往后找到第一个 $s_j = b$，可断言 $s_{i + 1} \cdots s_{j - 1} = a \cdots a$。反证：假设 $\exists s_k \ne a, k \in [i + 1, j - 1]$，则 $s_k = c$，不妨设它是最左边的一个。要满足条件 $4$，$t$ 中下一个 $c$ 的位置必须小于等于 $k$。但无论它在哪个位置，删除 “b” 后，$s$ 前缀（从 $s_i$ 开始）中第一个 “c” 之前 “a” 的个数至少比 $t$ 前缀（从 $t_i$ 开始）中第一个 “c” 之前 “a” 的个数多 $1$，这与条件 $2$ 矛盾。因此，断言成立。此时，只需将 $s_j$依次往前交换即可让 $s_i = t_i$。剩余的串等价于从原来的串中同时删去第一个 “b”。

2. 若 $t_i = c$。由条件 $2$，$s_i \ne a$。又 $s_i \ne t_i$，则 $s_i = b$。从 $s_i$ 往后找到第一个 $s_j = c$，可断言 $s_{i + 1} \cdots s_{j - 1} = b \cdots b$。反证：假设 $\exists s_k \ne b, k \in [i + 1, j - 1]$，则 $s_k = a$，不妨设它是最左边的一个。此时，删掉 “b”，$s_i$ 后第一个字符是 “a”，$t_i$ 后（包含自身）第一个字符是 “c”，这与条件 $2$ 矛盾。因此，断言成立。此时，只需将 $s_j$ 依次往前交换即可让 $s_i = t_i$。剩余的串等价于从原来的串中同时删去第一个 “c”。

无论哪种情况，剩余串仍满足以上四个条件，因此是递归子问题，可用相同方法处理，直到 $s_{i - 1} = t_{i - 1}$时，由于总字符相等，最后一个字符也必然相等。

结论法 $O(n)$

#include <iostream>
#include <vector>

#define endl "\n"

using namespace std;

const int N = 100010;

int n;
char s[N], t[N];

void solve() {
  cin >> n;
  cin >> s >> t;

  vector<int> sa, sc, ta, tc;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'a')
      sa.push_back(i);
    else if (s[i] == 'c')
      sc.push_back(i);
    if (t[i] == 'a')
      ta.push_back(i);
    else if (t[i] == 'c')
      tc.push_back(i);
  }

  bool ok = sa.size() == ta.size() && sc.size() == tc.size();
  for (int i = 0; ok && i < sa.size(); i++)
    ok = sa[i] <= ta[i];
  for (int i = 0; ok && i < sc.size(); i++)
    ok = sc[i] >= tc[i];

  int i = 0, j = 0;
  while (ok && i < n && j < n) {
    while (s[i] == 'b')
      i++;
    while (t[j] == 'b')
      j++;
    ok = s[i++] == t[j++];
  }

  cout << (ok ? "YES" : "NO") << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int q;
  cin >> q;
  while (q--)
    solve();
  return 0;
}

构造法 $O(n^2)$

#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
char s[N], t[N];

void solve() {
  cin >> n;
  cin >> s >> t;

  for (int i = 0; i < n; i++) {
    if (s[i] == t[i])
      continue;

    if (t[i] == 'a')
      break;

    char ti = 'b', si = 'a';
    if (t[i] == 'c')
      ti = 'c', si = 'b';

    if (s[i] != si)
      break;

    int j = i + 1;
    while (j < n && s[j] == si)
      j++;
    if (j == n || s[j] != ti)
      break;

    swap(s[i], s[j]);
  }

  if (!strcmp(s, t))
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int q;
  cin >> q;
  while (q--)
    solve();
  return 0;
}