誤読したーーーーーー操作は 1 回しか行えないものと思って悩んでた

問題概要

長さ $N$ の文字列 $S, T$ が与えられる。以下の操作を好きな回数だけ行うことで、 $S$ と $T$ とが一致する状態にすることが可能かどうかを判定せよ。

1 以上 $N$ 以下の整数 $l$ を定める
$S$ 中の連続する $l$ 文字をどこか選んで reverse する
$T$ 中の連続する $l$ 文字をどこか選んで reverse する ( $S$ と共通の部分でなくてよい)

制約

$1 \le N \le 2 \times 10^{5}$
文字はアルファベット小文字のみ

考えたこと

とりあえず S と T とで各文字の個数分布は等しいとして良い (そうでなければ NO)。その下で、ダメな場合を考えてみる。簡単な例だと

S = "ab"
T = "ba"

とかだと無理だ。"ab" は "ab" にしかなれない。このことから、何かしらのパリティが絡んでるという気持ちになる。

S, T の文字がすべて異なる場合 -> 転倒数のパリティ

ここで、S, T の文字がすべて異なる場合を考えてみる。このとき、S と T の順列としてのパリティ (転倒数の偶奇) が等しいことが必要十分なのではないかという予感がしてくる。

実際、一回の操作によって、S のパリティが変化するならば、T のパリティも変化する。S のパリティが変化しないならば、T のパリティも変化しない。よって、S と T のパリティが等しいことが必要条件である。

逆に、

任意の順列は、「隣接要素の swap」の合成で作れる
その回数の偶奇は、転倒数の偶奇に一致する

ということを思い出すと、十分条件でもあることがわかる。

S, T の文字に重複がある場合

文字の重複がある場合は、その順序を恣意的に変更できるため、パリティを自在に操れる。よって常に可能だ。

#include <bits/stdc++.h>
using namespace std;

long long tentou(const string &S) {
    long long res = 0;
    for (int i = 0; i < S.size(); ++i) {
        for (int j = i+1; j < S.size(); ++j) {
            if (S[i] > S[j]) ++res;
        }
    }
    return res;
}

bool solve(int N, const string &S, const string &T) {
    map<char, int> ms, mt;
    for (auto c : S) ms[c]++;
    for (auto c : T) mt[c]++;
    if (ms != mt) return false;
    for (auto it : ms) if (it.second > 1) return true;
    return (tentou(S) % 2) == (tentou(T) % 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int CASE;
    cin >> CASE;
    while (CASE--) {
        int N;
        string S, T;
        cin >> N >> S >> T;
        cout << (solve(N, S, T) ? "YES" : "NO") << endl;
    }
}