题目描述
难度分:2200
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤105)和两个长为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(nlog2n)。之后遍历一遍counter就可以计算出答案,遍历有序表的时候就是线性复杂度,在最差情况下有Σ2个key,本题中Σ=26。
综上,算法整体的时间复杂度为O(Σ2+nlog2n)。
空间复杂度
除了输入的s和t两个字符串,因此唯一的空间消耗就是counter,额外空间复杂度为O(Σ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;
}