算法分析
先判掉无解的情况:
- 在 $T$ 的末尾第一个
B
之后的所有A
存在某个和 $S$ 不匹配 - 在 $T$ 的开头第一个
A
之前的所有B
存在某个和 $S$ 不匹配
这部分和 ARC145A 很像
下面讨论有解的情况:
对于 $T$ 中的 B
和 $S$ 不匹配的情况,尽可能用前面 $T$ 中没有和 $S$ 匹配的 A
进行配对,如果没有的话就只能用前面已经匹配的 A
了,当然最后可能 $T$ 中还会剩下和 $S$ 不匹配的 A
,这时就把它和后面和 $T$ 中和 $S$ 匹配的 ‘B’ 凑对即可,本质上就是把 $T$ 中最左边的 A
和最右边的 B
当万能工具人即可
(是不是感觉很像括号配对?)
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n; string s, t;
cin >> n >> s >> t;
{
for (int i = n-1; i >= 0; --i) {
if (t[i] == 'B') break;
if (s[i] != 'A') {
puts("-1");
return 0;
}
}
rep(i, n) {
if (t[i] == 'A') break;
if (s[i] != 'B') {
puts("-1");
return 0;
}
}
}
int ans = 0, a = 0;
rep(i, n) if (s[i] != t[i]) {
++ans;
if (t[i] == 'A') ++a;
else {
if (a) --a, --ans;
}
}
cout << ans << '\n';
return 0;
}