题目描述
给定两个长度为 $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” 左移。
可发现如下性质:
-
“a” 只能右移,”c” 只能左移。
-
由于 “ac” 和 “ca” 都不能互换,因此 “a”、”c” 的相对位置不能发生改变。
因此,若 $s$ 能变成 $t$,则
-
两个串中 “b” 的数量一定相等。
-
删除所有 “b” 后,两个串应该相等。
-
$s$ 中第 $i$ 个 “a” 的下标应小于等于 $t$ 中第 $i$ 个 “a” 的下标。
-
$s$ 中第 $i$ 个 “c” 的下标应大于等于 $t$ 中第 $i$ 个 “c” 的下标。
证明:若上述条件成立,则 $s$ 一定能变成 $t$。
从前往后找到第一个不相等的字符 $s_i$ 和 $t_i$,此时需要移动 $s_i$,由于两个串的左边都相等,且剩余串仍然满足以上所有条件,只需考虑自此之后的递归子问题。由条件 $3$ 得 $t_i \ne a$:
-
若 $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”。
-
若 $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;
}