题目描述

难度分:$2200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和两个长为$n$的字符串$s$和$t$，只包含小写英文字母。

你可以执行如下操作任意次：

• 选择一个$[1,n]$中的整数$k$。
• 交换$s[0…k]$和$t[n-k…n-1]$，即$s$的长为$k$的前缀和$t$的长为$k$的后缀。

能否使$s=t$？输出YES或NO。

输入样例

7
3
cbc
aba
5
abcaa
cbabb
5
abcaa
cbabz
1
a
a
1
a
b
6
abadaa
adaaba
8
abcabdaa
adabcaba

输出样例

YES
YES
NO
YES
NO
NO
YES

算法

分组

首先，$s+t$的每种字母的出现次数必须是偶数，这是最终$s=t$的必要条件。

举例说明，假设$s$的前三个字母（$abc$）和$t$的后三个字母（$xyz$）交换

s = abc...
t = ...xyz

为方便看出规律，把$t$翻转，也就是

s = abc...
t'= zyx...

交换后就是

s = xyz...
t'= cba...

可以发现，对于$s$和$t’$，交换前和交换后，a和z始终是对应的，b和y始终是对应的，c和x始终是对应的。所以无论交换多少次，$s[i]$始终与$t’[i]$，也就是$t[n-1-i]$对应。（下标从$0$开始）这个结论也可以通过打表发现。

此外，在满足对应关系的前提下，$s$的任意排列我们是可以得到的：从$s$的排列$p$的最后一个字母（目标字母）开始，先把$s$中的目标字母翻转到最前面，再把$s$整个翻转，就可以把目标字母翻转到末尾。然后考虑$p$的倒数第二个字母，依此类推。

再从结果来看。示例$2$两个字符串都变成了

cbbaa
cbbaa

$s[0]$和$t[4]$是一对$($a$,$c$)$，$s[4]$和$t[0]$也是$($a$,$c$)$。所以要想让$s=t$，字母对$(s[i],t[n-1-i])$的出现次数必须是偶数，除了在$n$是奇数的情况下，允许有一对字母的出现次数是奇数。

复杂度分析

时间复杂度

遍历一遍字符串，构建出频数表$counter$，它的$key$是二元组$(s[i],t[n-1-i])$，因此使用有序表会更方便，构建频数表的时间复杂度为$O(nlog_2n)$。之后遍历一遍$counter$就可以计算出答案，遍历有序表的时候就是线性复杂度，在最差情况下有$\Sigma^2$个$key$，本题中$\Sigma=26$。

综上，算法整体的时间复杂度为$O(\Sigma^2+nlog_2n)$。

空间复杂度

除了输入的$s$和$t$两个字符串，因此唯一的空间消耗就是$counter$，额外空间复杂度为$O(\Sigma^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int T, n;
string s, t;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    while(T--) {
        cin >> n;
        cin >> s >> t;
        map<pair<char, char>, int> counter;
        for(int i = 0; i < n; i++) {
            counter[minmax(s[i], t[n - 1 - i])]++;
        }
        int odd = 0;
        bool ok = true;
        for(auto&[v, x]: counter) {
            if(x&1 && v.first != v.second) {
                ok = false;
                break;
            }
            odd += x&1;
        }
        if(odd > 1) ok = false;
        cout << (ok? "YES\n": "NO\n");
    }
    return 0;
}