题目描述

给定一个正整数 N 和两个长度为 N、由小写英文字母组成的字符串 S 和 T。

你可以执行任意次（可能为零次）以下操作：
* 选择两个小写英文字母 x 和 y，并将字符串 S 中 所有 的 x 替换为 y。

问是否可能通过上述操作将字符串 S 变为 T？如果可能，求所需的最小操作次数。

样例

输入:
6
afbfda
bkckbb

输出:
4

说明：可以通过 4 次操作将 S 变为 T：
1. x=b, y=c. S 变为 afcfda.
2. x=a, y=b. S 变为 bfcfdb.
3. x=f, y=k. S 变为 bkckdb.
4. x=d, y=b. S 变为 bkckbb (等于 T).
无法用少于 4 次操作完成，所以最小次数是 4。

输入:
4
abac
abrc

输出:
-1

说明：S[2] 是 a，T[2] 是 r；S[0] 是 a，T[0] 是 a。由于 S 中所有的 ‘a’ 必须同时变成同一个字符，但目标 T 中对应的位置要求 ‘a’ 变成 ‘r’ 和 ‘a’ 变成 ‘a’，这是矛盾的，因此不可能。

算法 (并查集 / 图论)

$O(N + |\Sigma|)$ 其中 $|\Sigma|=26$

思路分析

1. 操作的性质: 核心在于操作 “将 S 中 所有 的 x 替换为 y“。这意味着，如果初始时 S[i] == S[j]，那么在任意次操作之后，S[i] 和 S[j] 的字符必须始终保持相同。

2. 必要条件: 基于上述性质，一个必要条件是：对于所有 0 <= i, j < N，如果 S[i] == S[j]，那么必须有 T[i] == T[j]。如果存在某个字符 c，它在 S 中的某些位置 i 对应 T 中的字符 d1，而在另一些位置 j 对应 T 中的字符 d2，且 d1 != d2，那么就不可能将 S 变成 T。

3. 映射关系: 我们可以遍历 S 和 T，找出每个字符 x (来自 S) 需要变成哪个字符 y (来自 T)。我们可以用一个数组 f[0...25] 来记录这种映射关系，f[x - 'a'] = y - 'a' 表示字符 x 最终需要变成 y。

   • 遍历 i 从 0 到 N-1。令 x = S[i] - 'a' 和 y = T[i] - 'a'。
   • 检查一致性：
     • 如果 f[x] 尚未设置 (例如，初始化为 -1)，则设置 f[x] = y。
     • 如果 f[x] 已经设置，并且 f[x] != y，则出现了矛盾（同一个原始字符 x 需要变成不同的目标字符），说明不可能将 S 变为 T，输出 -1 并退出。
   • 如果遍历完成没有发现矛盾，f 就定义了从 S 中出现的字符到 T 中对应字符的必要转换关系。

4. 操作次数与转换关系: 现在的问题是，如何用最少的操作次数实现 f 定义的这些转换？

   • 一次操作 replace(x, y) 可以看作是将字符 x 的 “身份” 永久地变成了 y。
   • 考虑 f 定义的转换 x -> y (即 f[x] = y)。如果 x == y，这个转换不需要任何操作。如果 x != y，我们至少需要一次操作来改变 x。
   • 这些转换关系 x -> y (其中 x != y) 可以在 26 个字母上构成一个 功能图 (functional graph)。每个节点最多有一个出度（由 f 定义）。这种图的结构是若干个连通分量，每个连通分量包含若干棵（可能为空的）有向树，这些树的根最终指向一个环（环的长度可能为 1，即自环）。
   • 例如：a -> b, b -> c, c -> c 构成一个分量。d -> e, e -> d 构成另一个分量（一个环）。g -> g 是一个平凡分量。

5. 使用并查集 (DSU) 建模: 我们可以用并查集来追踪哪些字符最终需要变成同一个字符。如果 f[x] = y 且 x != y，这意味着 x 和 y 最终必须是同一个字符。我们将 x 和 y 合并到同一个集合中：dsu.merge(x, y)。

   • 合并完成后，同一个集合中的所有字符，在最终状态 T 中必须都对应同一个字符（这一点已由步骤 3 的一致性检查保证）。

6. 计算最小操作次数:

   • 对于每个 x，如果 f[x] != -1 且 f[x] != x，我们就需要至少一次操作来启动 x 的转变。我们可以初步计算操作次数 ans 为所有满足此条件的 x 的数量。
   • 考虑一个连通分量（DSU 集合）。如果这个分量在功能图 f 中对应的是一棵树或一个以自环结尾的结构（例如 a -> b -> c -> c），那么初步计算的 ans（对于这个分量是 2 次，因为 a != b 且 b != c）就是所需的操作次数。我们可以执行 replace(a, b)，然后 replace(b, c)。
   • 特殊情况：环: 如果一个连通分量在功能图 f 中对应一个长度大于 1 的环（例如 a -> b -> c -> a），会发生什么？
     • 初步计算 ans 会包含环上每条边对应的操作（例如，a != b, b != c, c != a 贡献 3 次）。
     • 但是，直接执行 replace(a, b), replace(b, c), replace(c, a) 是不行的。例如，replace(a, b) 后，所有 a 都变成了 b。
     • 处理环需要一个额外的 “临时” 字符。例如，要实现 a -> b -> c -> a：
       1. 选择一个临时字符 t (不在环 a, b, c 中)。
       2. replace(a, t) (S 中 a 变 t)
       3. replace(b, a) (S 中 b 变 a)
       4. replace(c, b) (S 中 c 变 b)
       5. replace(t, c) (S 中 t 变 c)
          这样需要 环长 + 1 次操作。而我们初步计算的 ans 只计算了 环长 次。因此，每个长度大于 1 的环需要额外增加 1 次操作。
   • 如何检测环: 在并查集结构中，一个连通分量 i (以 i 为根) 对应功能图中的一个纯环（长度 > 1）当且仅当：
     • 集合大小 dsu.size(i) 大于 1。
     • 集合中的 每个 元素 j 都是某个转换 f[x] = j 的目标 (即 vis[j] 为 true，其中 vis[k] 标记字符 k 是否是某个 f[x]=k 的目标)。用 e[i] 记录集合 i 中有多少个元素是目标。如果 e[i] == dsu.size(i)，则说明集合中的每个元素都有一个指向它的映射（在功能图中入度至少为 1），这结合功能图的性质（出度最多为 1）以及连通性（DSU 保证），意味着这个分量必然是一个纯环。
   • 所以，最终的操作次数 = (初步计算的 ans) + (纯环的数量)。

7. 无法使用临时字符的情况: 处理环需要一个临时字符 t。如果所有 26 个小写字母都参与了转换（即它们都在某个非平凡的 DSU 集合中，或者说，它们都是某个 f[x]=y 中的 x 或 y），并且我们还需要执行环交换，那么可能没有可用的临时字符 t。

   • 如何判断所有字符都参与了？我们可以检查是否所有 26 个字符都是某个 f[x] = y 的目标 (即 vis[y] 为 true)。如果 std::count(vis.begin(), vis.end(), true) == 26，说明所有 26 个字符都是某个转换的目标。
   • 在这种情况下（所有 26 个字符都是目标），功能图 f（限制在有定义的 x 上）必然构成一个覆盖所有 26 个字母的映射。由于输入集合和输出集合都是 26 个字母，这实际上意味着 f 是一个对 26 个字母的 置换 (permutation)。
   • 一个置换总是可以分解为不相交的环。如果 S != T，那么这个置换中必然存在长度大于 1 的环。
   • 因此，如果 S != T 且所有 26 个字符都是目标 (count(vis) == 26)，那么必然存在需要额外操作的环，并且没有临时字符可用。此时应输出 -1。

8. 算法总结:

   1. 检查 S == T。若是，输出 0。
   2. 构建映射 f，同时检查一致性。若不一致，输出 -1。
   3. 初始化并查集 DSU(26)，计数器 ans = 0，标记数组 vis[26]。
   4. 遍历 i 从 0 到 25：
      • 如果 f[i] != -1，标记 vis[f[i]] = true。
      • 如果 f[i] != -1 且 f[i] != i，则 ans++ 并且 dsu.merge(i, f[i])。
   5. 检查是否所有 26 个字符都是目标：if (std::count(vis.begin(), vis.end(), true) == 26)。若是，输出 -1 (因为 S!=T 且无法使用临时字符处理环)。
   6. 计算每个 DSU 根 i 的 e[i]，表示其集合中有多少个元素是目标 (vis[j] == true 且 dsu.find(j) == i)。
   7. 遍历每个 DSU 根 i (即 dsu.find(i) == i)：
      • 如果 e[i] > 1 且 e[i] == dsu.size(i) (表示这是一个纯环，长度 > 1)，则 ans++。
   8. 输出 ans。

时间复杂度

• 构建映射 f: O(N)。
• 初始化和操作并查集、vis 数组、计算 e 数组、最后检查环：这些都只涉及 26 个字母，时间复杂度是 O(|\Sigma| * \alpha(|\Sigma|)) 或近似 O(|\Sigma|)，其中 |\Sigma| = 26，\alpha 是反阿克曼函数，几乎是常数。
• 总时间复杂度主要是 O(N)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using i64 = long long;
// using u64 = unsigned long long; // 未使用
// using u32 = unsigned; // 未使用
// using u128 = unsigned __int128; // 未使用

// 并查集 (Disjoint Set Union) 结构体
struct DSU {
    std::vector<int> f, siz; // f: 父节点数组, siz: 集合大小数组

    DSU() {} // 默认构造函数
    DSU(int n) { // 带大小的构造函数
        init(n);
    }

    // 初始化并查集，大小为 n
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0); // 初始化父节点为自己 (0, 1, ..., n-1)
        siz.assign(n, 1); // 初始化每个集合大小为 1
    }

    // 查找元素 x 所在集合的根节点 (带路径压缩)
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]]; // 路径压缩
        }
        return x;
    }

    // 判断 x 和 y 是否在同一个集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 和 y 所在的集合 (按大小合并)
    // 返回 true 如果成功合并 (原本不在同一集合), false 如果已在同一集合
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false; // 已经在同一集合
        }
        // 按大小合并：将小的集合合并到大的集合
        if (siz[x] < siz[y]) std::swap(x, y); // 保证 x 是较大的集合
        siz[x] += siz[y]; // 更新大集合的大小
        f[y] = x; // 将小集合的根指向大集合的根
        return true;
    }

    // 返回元素 x 所在集合的大小
    int size(int x) {
        return siz[find(x)];
    }
};

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    std::ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    std::cin.tie(nullptr);

    int N; // 字符串长度
    std::cin >> N;

    std::string S, T; // 输入字符串 S 和 T
    std::cin >> S >> T;

    // 如果 S 和 T 已经相同，不需要操作
    if (S == T) {
        std::cout << 0 << "\n";
        return 0;
    }

    // f[x] 存储字符 x (0-25) 需要变成的字符 y (0-25)。-1 表示未定义。
    std::vector<int> f(26, -1);
    // 遍历字符串，构建映射 f 并检查一致性
    for (int i = 0; i < N; i++) {
        int x = S[i] - 'a'; // 原始字符
        int y = T[i] - 'a'; // 目标字符
        if (f[x] == -1) {
            // 第一次遇到 x，记录其映射
            f[x] = y;
        } else if (f[x] != y) {
            // 发现矛盾：x 需要变成 f[x]，但现在又需要变成 y (y != f[x])
            std::cout << -1 << "\n"; // 不可能
            return 0;
        }
    }

    int ans = 0; // 初始化最小操作次数
    std::vector<bool> vis(26); // vis[i] 标记字符 i 是否是某个 f[x]=i 的目标
    DSU dsu(26); // 初始化 26 个字母的并查集

    // 遍历所有字母，计算初步操作数并构建并查集结构
    for (int i = 0; i < 26; i++) {
        if (f[i] != -1) {
            // 如果 f[i] 有定义，则字符 f[i] 是一个目标
            vis[f[i]] = true;
        }
        // 如果 f[i] 定义了非自环的转换 (i -> f[i] 且 i != f[i])
        if (f[i] != -1 && f[i] != i) {
            ans++; // 需要一次操作来启动转换
            dsu.merge(i, f[i]); // 将 i 和 f[i] 合并到同一集合
        }
    }

    // 检查是否所有 26 个字符都是目标
    // 如果是，并且 S != T，说明 f 是一个包含非平凡环的置换
    // 由于没有临时字符可用，无法完成环转换
    if (std::count(vis.begin(), vis.end(), true) == 26) {
        std::cout << -1 << "\n"; // 不可能
        return 0;
    }

    // e[root] 记录根为 root 的集合中有多少个元素是目标 (vis[j]=true)
    std::vector<int> e(26);
    for (int i = 0; i < 26; i++) {
        if (vis[i]) { // 如果字符 i 是目标
            e[dsu.find(i)]++; // 增加其所在集合根节点的计数
        }
    }

    // 遍历所有 DSU 集合的根节点
    for (int i = 0; i < 26; i++) {
        // 如果 i 是一个根节点 (i == dsu.find(i))
        // 并且该集合构成了纯环 (e[i] > 1 保证大小 > 1, e[i] == dsu.size(i) 保证是纯环)
        if (dsu.find(i) == i && e[i] > 1 && e[i] == dsu.size(i)) {
            ans++; // 需要一次额外的操作来处理这个环
        }
    }

    // 输出最终的最小操作次数
    std::cout << ans << "\n";

    return 0; // 程序正常结束
}