丁寧な場合分けの考察を要求される問題です。本解説中、文字列 \(X\) の \(i\) 文字目のことを \(X_i\) と表記します。

まず、\(S_i=S_j\) かつ \(T_i\neq T_j\) であるような \(i,j\ (i\neq j)\) が存在する場合、答えは \(-1\) です。なぜなら、どのような操作を行なっても、\(S\) の中の等しい \(2\) 文字が相異なる \(2\) 文字に変化することはないからです。

以下、上記のようなケースは除外して考えます。すなわち、すべての \(i,j\) について \(S_i=S_j \Rightarrow T_i=T_j\) が成立すると仮定します。

このとき、以下のように定義される有向グラフ \(G\) を考えることができます。

• \(G\) の頂点集合は \(26\) 頂点からなり、英小文字 a, b, …, z のラベルがつけられている。
• \(G\) には、\(S_i=x\) かつ \(T_i=y\) であるような \(i\ (1\leq i\leq N)\) が存在する場合、またその場合に限り、頂点 \(x\rightarrow y\) の辺が存在する。

このとき、「すべての \(i,j\) について \(S_i=S_j \Rightarrow T_i=T_j\)」という性質から、各頂点の出次数は \(0\) または \(1\) であることが言えます。

さらに、グラフ \(G\) の頂点上にいくつかのコマを乗せることを考えます。最初、頂点 \(c\) には、\(S_i=c\) なる \(i\) が存在する場合 (\(\Leftrightarrow c\) の出次数が \(1\) である場合) コマが \(1\) つ乗っていて、そうでない場合何も乗っていません。

以下の図は \(G\) の一例を表したものであり、\(S=\) bcdefghij, \(T=\) aaccghfgg の場合などに該当します。これ以外にも孤立点 k, l, …, z が存在しますが、省略されています。赤い四角形はコマを表しています。

このグラフとコマの概念を利用すると、問題を以下のように言い換えることができます。

• グラフ \(G\) およびいくつかのコマの初期位置が与えられる。各コマには 目的地 が定められており、そのコマの初期位置の頂点から唯一辺が伸びている先の頂点に一致する。以下の操作を繰り返すことで、すべてのコマを各々の目的地へ移動させたい。そのようなことは可能か？可能ならば操作回数の最小値はいくつか？
  • 操作：\(2\) つの頂点 \(x,y\ (x\neq y)\) を選び、頂点 \(x\) 上にあるコマをすべて頂点 \(y\) 上に移動させる。

この問題を解く上で肝となるのは、「複数のコマが同じ頂点上に置かれた場合、それらのコマは以降二度と別々の頂点に置かれることはない」という点です。つまり、目的地の相異なるコマ同士を同じ頂点上においてはいけません。この制約を満たしたままうまくコマを移動させるにはどうしたら良いでしょうか。

初期状態において、グラフ \(G\) およびコマの配置がどのようになっているかを考えます。各連結成分は以下の \(6\) タイプに分別されます：

• A: 孤立点
• B: 長さ \(1\) のサイクル
• C: 長さ \(2\) 以上のサイクル
• D: 根付き木
• E: 長さ \(1\) のサイクルおよびそれに付着する根付き木
• F: 長さ \(2\) 以上のサイクルおよびそれに付着するいくつかの根付き木

最初に結論を述べます。答えは以下の通りです：

• \(G\) が \(0\) 個以上のタイプ B の連結成分と \(1\) 個以上のタイプ C の連結成分のみからなる場合、\(-1\)
• そうでない場合、初期位置と目的地が異なるコマの個数にタイプ C の連結成分の個数を足したもの。すなわち、タイプ X の連結成分の個数を \(x\) とおいたとき、\(N-(a+b+d+e)+c\)

一つ目のケースについて、「\(G\) が \(0\) 個以上のタイプ B の連結成分と \(1\) 個以上のタイプ C の連結成分のみからなる」ことは、頂点 \(c\) から辺が伸びる先の頂点を \(A_c\) (辺が存在しなければ \(-1\)) としたとき、「\((A_a,A_b,\dots,A_z)\) が \((a,b,\dots,z)\) の並び替えでありかつ \(S\neq T\) である」ことと同値です。二つ目のケースについて、タイプ C の連結成分の個数を求めるには、サイズが \(2\) 以上かつ全頂点の入次数が \(1\) であるような連結成分の個数を求めればよいです。\(G\) の頂点数は \(26\) と小さいので、多項式時間解法であればほとんどどのような解法であっても正答することができます。

最後に略証を記します。

一つ目のケースについては、最初にどのような操作を行なったとしても、目的地の異なる二つのコマが同じ頂点に位置してしまうことから従います。

二つ目のケースについて、その値が答えの下限であることは、初期位置と目的地が異なる各コマにつき最低一回は操作が必要なこと、およびタイプ C の連結成分内の全コマをコマ数と等しい操作回数で移動させることはできない（直観的には、一度いずれかのコマをサイクルから退避させる必要がある）ことから従います。

二つ目のケースについて、その値が答えの上限であることは、実際に操作方法を構築できることから従います。まず、タイプ A, B, D, E の各連結成分について、根から近い順に各コマを目的地へ移動させます。次に、タイプ F の各連結成分については、サイクル上の適切なコマ \(1\) つをそのコマと目的地が等しいサイクル外の別のコマと合流させることで、タイプ D に帰着できます。最後にタイプ C については、タイプ A, D, E, F の連結成分を処理することによって生まれた空きマスにコマを \(1\) つ移動させると、タイプ D に帰着できます。

実装例 (C++) :

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

const int C = 26;

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    if (s == t) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> to(C, -1);
    for (int i = 0; i < n; i++) {
        int sc = s[i] - 'a';
        int tc = t[i] - 'a';
        if (to[sc] != -1 and to[sc] != tc) {
            cout << -1 << endl;
            return 0;
        }
        to[sc] = tc;
    }
    bool is_perm = true;
    vector<int> tmp = to;
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < C; i++) {
        is_perm &= (tmp[i] == i);
    }
    if (is_perm) {
        cout << -1 << endl;
        return 0;
    }
    int ans = 0;
    vector<int> in_deg(C);
    dsu uf(C);
    for (int i = 0; i < C; i++) {
        if (to[i] != -1) {
            if (to[i] != i) {
                ans++;
            }
            in_deg[to[i]]++;
            uf.merge(i, to[i]);
        }
    }
    vector<vector<int>> groups = uf.groups();
    for (const vector<int> &g: groups) {
        bool is_cycle = true;
        for (int i: g) {
            is_cycle &= (in_deg[i] == 1);
        }
        if (is_cycle and g.size() > 1) {
            ans++;
        }
    }
    cout << ans << endl;
}