LeetCode 1202. 交换字符串中的元素

2023-04-23 HGNULB 约 13 分钟

文章信息 6 个分类 7 个标签

分类

题目描述

✅ 1202. 交换字符串中的元素

题意分析

给一个字符串 s 和若干下标对 pairs，每个 pairs[i] = [a, b] 表示可以交换 s[a] 与 s[b]。每一对可以使用任意多次，求能得到的字典序最小的字符串。

「可以使用任意多次」是最关键的一句话。它意味着交换关系是可传递的：若能换 (0,1) 又能换 (1,2)，那么通过若干次操作就能把 0 号位的字符送到 2 号位——用 (0,1)、(1,2)、(0,1) 三步即可实现 0 与 2 的对调。所以真正起作用的不是每一对本身，而是这些对连成了哪些「可互相到达」的下标集合。

顺着这条线，问题就从「操作序列」变成了「分组」：把下标看成图的顶点、每个 pair 看成一条无向边，同一个连通分量里的下标可以任意重排（连通图上的换位生成整个对称群，用相邻对换即可构造任意排列）。而不同分量之间永远无法交换——这是硬边界。

一旦确定「分量内可任意重排」，最小字典序的做法就唯一了：每个分量各自把持有的字符从小到大排好，再按下标从小到大填回去。分量之间互不影响，各自最优即全局最优。

约束：s 长度和 pairs 数量都可达 $10^5$。这个规模允许 $O((n + m)\alpha + n \log n)$，但不允许对每个分量做任何平方级操作。

边界：pairs 可能为空，此时每个下标自成一个分量，答案就是原串；某些下标可能不出现在任何 pair 中，它们同样自成分量、字符原地不动；同一对可能重复出现，合并时自然幂等。

解法：并查集分组 + 组内排序

核心思路

先看暴力：把 pairs 当成可执行的操作，做 BFS 搜索所有能到达的字符串取最小。状态数是 s 的排列数，指数级爆炸，$n = 10^5$ 时连一步都走不完。瓶颈在于把「可交换」当成了动作序列，而不是结构性质。

转换视角：既然交换可以无限次使用，就不必关心「怎么换」，只需要知道「哪些位置最终可以互换」。这就是连通性问题。

求连通分量可以建图后 DFS/BFS，也可以用并查集。这里的边已经逐条给出，只需合并端点，并不需要之后遍历邻居，因此并查集能直接消费 pairs，省去邻接表；路径压缩配合按大小合并后，单次操作的均摊复杂度为 $O(\alpha(n))$。

算法三步：

建组：对每个 pair 调 union(a, b)。处理完所有对之后，find(i) 就是下标 i 所属分量的代表元。

收集：遍历所有下标 i，按 find(i) 把它们分进哈希表 groups: 根 → 该分量的下标列表。因为遍历顺序是 i 递增，每个列表天然按下标升序排列。

组内重排：对每个分量，取出这些下标上的字符排序，再按升序的下标依次填回。

建组阶段的不变量是：处理完任意前缀的交换对后，find(i) == find(j) 当且仅当 i、j 已被这些边连通。所有边处理完后，并查集恰好给出完整图的连通分量。连通分量内任意两点之间都有路径；沿路径正向交换到终点，再沿除最后一条外的边反向交换，可以对调两个端点并恢复中间字符，因此分量内可以生成任意排列。

为什么「分量内排序后按下标升序填回」就是字典序最小？对某个分量，假设较小下标放了较大字符，而较大下标放了较小字符，交换两者会让字符串在第一个不同位置变小。因此最优排列中不可能存在这种逆序，字符升序与下标升序必须一一对应。不同分量不能交换字符，也没有资源竞争，所以各分量分别最优就得到全局最优。

实现中 find 用路径减半压缩查询路径，union 按 size 把小树挂到大树下，避免并查集树在不利的合并顺序下过深。

解题步骤

初始化并查集：parent[i] = i、size[i] = 1，共 n 个元素（下标 0 到 n-1）。每个下标先各自成组，对应「没有任何交换对时字符原地不动」。

逐对合并：uf.union(p.get(0), p.get(1))。不需要判重——重复的对第二次合并时两端已同根，union 内部直接返回，天然幂等。

按根收集下标：遍历 i 从 0 到 n-1，groups.computeIfAbsent(uf.find(i), ...).add(i)。必须用 find(i) 而不是 parent[i]：parent[i] 只是直接父亲，可能不是根；用它分组会把同一分量拆成好几份。这一步遍历顺序递增，所以每个列表本身已经有序。

取出分量内的字符并排序：对每个分量的下标列表，把 res[idx] 收进一个字符列表并升序排序。排序是把「最小字符优先」这个贪心落到实处。

按下标升序填回：res[idxs.get(i)] = chars[i]。下标是按 i = 0..n-1 收集的，列表天然递增，不要再重复排序；只需把该分量的字符排好序后逐一对应。

组装结果：new String(res)。全程在字符数组上原地修改，不产生中间字符串。

以 s = "dcab"、pairs = [[0,3],[1,2]] 走一遍（答案 "bacd"）：

合并：union(0,3) 让 0 与 3 同组；union(1,2) 让 1 与 2 同组。得到两个分量 {0,3} 与 {1,2}。

收集：i = 0 根为 0（假设 0 成为代表），归入 {0}；i = 1 归入另一组；i = 2 与 1 同根，加入该组得 {1,2}；i = 3 与 0 同根，得 {0,3}。

处理分量 {0,3}：字符是 s[0]='d'、s[3]='b'，排序得 ['b','d']；按下标升序填回：res[0]='b'、res[3]='d'。

处理分量 {1,2}：字符是 'c'、'a'，排序得 ['a','c']；填回 res[1]='a'、res[2]='c'。

结果 "bacd"。可以验证：'d' 与 'b' 通过 (0,3) 一次交换即可对调；'c' 与 'a' 通过 (1,2) 对调。两个分量互不干扰。

再以 s = "dcab"、pairs = [[0,3],[1,2],[0,2]] 走一遍（答案 "abcd"）：

union(0,3)、union(1,2)、union(0,2) 把两个分量连成了一个 {0,1,2,3}。虽然 pairs 里并没有 (0,1) 这一对，但 0 与 1 通过 0-2-1 相连——传递性正是这一步体现出来的，这也是必须用并查集而非直接按 pair 交换的原因。

分量内字符是 d,c,a,b，排序得 a,b,c,d；下标升序 0,1,2,3；填回得 "abcd"。

再以 s = "cba"、pairs = [[0,1],[1,2]] 走一遍（答案 "abc"）：三个下标连成一个分量，字符 c,b,a 排序为 a,b,c，填回得 "abc"。若误以为「只能按给定的对逐次交换、且每对只能用一次」，就只能得到 "bca" 或 "cab" 之类，无法达到最优。

最后看分组用错的后果：依次合并 (0,1)、(2,3)、(0,2) 后，四个下标已经连通，但 parent[3] 仍可能是 2，而 2 的根已变成 0。若直接按 parent[i] 分组，下标 3 会被错误拆出；调用 find(i) 才能拿到最终代表元 0。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);
        // 交换可无限次使用，等价于把下标按可达性并成连通分量。
        for (List<Integer> p : pairs) {
            uf.union(p.get(0), p.get(1));
        }

        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 必须用 find(i) 取根，parent[i] 只是直接父亲。
            int root = uf.find(i);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
        }

        char[] res = s.toCharArray();
        for (List<Integer> idxs : groups.values()) {
            char[] chars = new char[idxs.size()];
            for (int i = 0; i < idxs.size(); i++) {
                chars[i] = s.charAt(idxs.get(i));
            }
            // 小字符配小下标，即为该分量能达到的字典序最小。
            Arrays.sort(chars);
            for (int i = 0; i < idxs.size(); i++) {
                res[idxs.get(i)] = chars[i];
            }
        }

        return new String(res);
    }

    static class UnionFind {
        int[] parent;
        int[] size;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                // 路径减半，就地压扁查找路径。
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        void union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return;
            }
            // 按大小合并，小树挂到大树下。
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
}

import "sort"

type UnionFind struct {
	parent []int
	size   []int
}

func newUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	size := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
		size[i] = 1
	}
	return &UnionFind{parent: parent, size: size}
}

func (uf *UnionFind) find(x int) int {
	for x != uf.parent[x] {
		// 路径减半，就地压扁查找路径。
		uf.parent[x] = uf.parent[uf.parent[x]]
		x = uf.parent[x]
	}
	return x
}

func (uf *UnionFind) union(a, b int) {
	ra := uf.find(a)
	rb := uf.find(b)
	if ra == rb {
		return
	}
	// 按大小合并，小树挂到大树下。
	if uf.size[ra] < uf.size[rb] {
		ra, rb = rb, ra
	}
	uf.parent[rb] = ra
	uf.size[ra] += uf.size[rb]
}

func smallestStringWithSwaps(s string, pairs [][]int) string {
	n := len(s)
	uf := newUnionFind(n)
	// 交换可无限次使用，等价于把下标按可达性并成连通分量。
	for _, p := range pairs {
		uf.union(p[0], p[1])
	}

	groups := make(map[int][]int)
	for i := 0; i < n; i++ {
		// 必须用 find(i) 取根，parent[i] 只是直接父亲。
		root := uf.find(i)
		groups[root] = append(groups[root], i)
	}

	res := []byte(s)
	for _, idxs := range groups {
		chars := make([]byte, len(idxs))
		for i, idx := range idxs {
			chars[i] = res[idx]
		}
		// 小字符配小下标，即为该分量能达到的字典序最小。
		sort.Slice(chars, func(i, j int) bool {
			return chars[i] < chars[j]
		})
		for i, idx := range idxs {
			res[idx] = chars[i]
		}
	}

	return string(res)
}

复杂度分析

时间复杂度：$O((m+n)\alpha(n) + n \log n)$，其中 $n$ 为字符串长度、$m$ 为 pairs 数量。合并 $m$ 次、分组时查找 $n$ 次；各分量内部排序的总元素数为 $n$，分开排序的总代价不超过 $O(n \log n)$。

空间复杂度：$O(n)$，并查集的两个数组各 $O(n)$，分组哈希表存下全部 $n$ 个下标，结果字符数组 $O(n)$。注意这里不需要建邻接表，省下了 $O(m)$ 的边存储。

关键点总结

「操作可以重复无限次」是把交换问题转化为连通性问题的开关：只要能重复使用，交换关系就具有传递性，真正决定答案的是连通分量而非具体的对。

连通分量内的下标可以任意重排（相邻对换生成全排列），分量之间完全隔离——这条结论把一个全局最优化问题拆成了若干互不影响的独立子问题。

独立子问题各自贪心即全局最优：每个分量把最小的字符放在最靠左的位置，因为字典序是逐位比较的，而分量之间没有资源竞争。

分组时必须用 find(i) 取根，不能用 parent[i]——后者只是直接父亲，会把同一分量拆散。这是并查集使用中最高频的错误。

路径压缩与按大小/秩合并共同保证近似常数的均摊操作成本；二者都是只改并查集内部形状，不改变分组结果。

并查集相对 DFS 建图的优势在于不必显式存储 $m$ 条边，在 $m$ 很大时省下可观内存。

面试表达顺序应是「无限次交换 ⇒ 连通分量 ⇒ 分量内任意排列 ⇒ 小字符配小下标」，并能用路径上的交换说明任意两个位置为何可换。

易错点总结

错误写法：分组时用 uf.parent[i] 而不是 uf.find(i)。例如依次合并 (0,1)、(2,3)、(0,2) 后，parent[3] 仍可能是 2，而真正的根是 0；直接按父节点分组会把同一分量拆开。

错误写法：只按 pairs 顺序做一轮局部交换。s = "cba"、pairs = [[0,1],[1,2]] 时会得到 "bac"，但连通分量允许任意重排，正确答案是 "abc"。

错误写法：认为只有直接出现在 pairs 里的两个下标才能互换。用例 s = "cba"、pairs = [[0,1],[1,2]]：忽略传递性会认为 0 与 2 不能换，返回 "bca"，正确答案是 "abc"。

错误写法：填回时下标列表未按升序。用例 s = "dcab"、pairs = [[0,3]]：若下标列表是 [3,0]，排序后的字符 ['b','d'] 会填成 res[3]='b'、res[0]='d'，得到 "dcab" 而不是 "bacd"——字符虽然对，位置全反了。

错误写法：对整个字符串排序后直接返回。用例 s = "dcab"、pairs = [[0,3],[1,2]]：返回 "abcd"，但 0 号位与 1 号位之间没有交换通路，这个结果不可达，正确答案是 "bacd"。

错误写法：把字符按哈希表遍历顺序顺次拼接，而不是写回原下标。分量 {0,3}、{1,2} 的下标不连续，拼接会直接改变位置语义。

错误写法：并查集数组按 pairs 中出现的最大下标开辟。s = "abc"、pairs = [[0,1]] 时孤立下标 2 仍然存在，数组必须按字符串长度创建。

相似题目

题目	难度	考察点
547. 省份数量	中等	只需数出连通分量个数，是本题第一步的最小化练习
721. 账户合并	中等	同样是「并查集分组 + 组内排序输出」，但需要邮箱到下标的映射层
990. 等式方程的可满足性	中等	先合并所有等式再校验不等式，考察「先建组后判定」的处理顺序
684. 冗余连接	中等	用合并是否失败判环，是并查集的另一种典型用法
839. 相似字符串组	困难	边不是给定的而要两两判定相似性，重点在如何降低建边代价
765. 情侣牵手	困难	用「分量大小减一」直接算出最少交换次数，是连通分量的计数型应用
323. 无向图中连通分量的数目	中等	并查集与 DFS 两种求分量方式的直接对照