题目描述
思路解析
一句话答案：LeetCode 1202 交换字符串中的元素：能反复对调的下标经传递连成一组，用并查集分组后把每组字符排升序、填回升序下标，就得到字典序最小串，时间 O((n+m)α+n log n)。
字典序最小，可动的到底是哪些位置
给一个字符串 s 和若干个下标对 pairs，每一对里的两个位置可以无限次互相对调。要问把这些交换用到头，s 能变成的字典序最小串是什么。题面 s="dcab"、pairs=[[0,3],[1,2]]，答案是 "bacd"；若再补一对 [0,2]，四个位置连成一片，答案能小到 "abcd"。要留意：能换的是位置，不是某个字母，相同字母落在不同位置未必能凑到一块。
一对一对手动交换，行不通在哪
pairs 只给出几对下标，真按它一对一对地换、再枚举所有交换顺序，组合数会随对数指数膨胀，根本试不完。何况一对能换无数次，还能借共同下标一环扣一环传下去：0 和 2 能换、2 和 4 能换，0 和 4 没直接配过对，也能通过 2 挪到一起。手动模拟数不清顺序，也抓不住这种间接连通。
先弄清哪些下标属于同一组
把每个下标看成一个点，每对 pairs 看成把两个点连起来。能直接或间接连到一起的下标，构成一个连通分量——里头任意两下标都能顺着对调互相走到，这些位置上的字符可以任意重排。求这种分组用并查集最省事：并查集，即把互相能换到的下标一点点收拢到同一个代表下面，合并时让一个的代表指向另一个，查代表时顺着指向找到根。m 对下标合并完，每个下标归哪组就定死了。
组内排升序，再按下标从小到大填
分组只解决了谁和谁能换，还得摆成字典序最小。对每一组：把组里所有位置上的字符抽出来排成升序，再把组里的下标也从小到大排好，然后让最小字符落最小下标、次小落次小，一一对应。字典序看的是从左往右第一个不同的位置，越靠前的下标越该放小字符，每组内部都让小字符占小位置，整串就压到最小。参考代码换了个等价写法：每组字符降序存着，填回时从尾部弹出最小的，落点完全一样。
"dcab" 配上 [[0,3],[1,2]] 怎么排
按题面走一遍。s="dcab"，下标 0 到 3 上是 d、c、a、b。第一对 [0,3] 把 0、3 并一组，第二对 [1,2] 把 1、2 并一组，得两组：{0,3} 和 {1,2}。看 {0,3}：位置 0 是 d、位置 3 是 b，两个字符排升序是 b、d，下标升序是 0、3，于是 b 进 0、d 进 3。看 {1,2}：位置 1 是 c、位置 2 是 a，排升序是 a、c，下标升序是 1、2，于是 a 进 1、c 进 2。四个位置落定 b、a、c、d，读出来正是 "bacd"。若再加一对 [0,2]，四位连成一整组，d、c、a、b 整体排成 a、b、c、d 填回，收紧到 "abcd"。
复杂度与两处一写就崩的地方
设串长 n、下标对数 m。m 次合并加上按下标查根，路径压缩后近似线性，是 O((n+m)α)，α 增长极慢，当常数看即可；各组字符加起来总共 n 个，排序合计 O(n log n)，两者相加是总时间。空间上 parent 数组和分组存放的字符都随串长走，是 O(n)。有两处一写就崩：并查集若建在字符上而不是下标上，相同字母在不同位置会被硬并成一组，答案立刻散架；字符排好序却忘了按下标升序填回，只排字符不管位置，逐位最小就守不住。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住两件事:并查集连的是索引不是字符;同一组内字符可自由重排,按升序填回升序索引就最小。下面一帧帧套它。
初始 · 6 个索引各自独立：先把 6 个位置摆成 6 个节点,标号 0 到 5,对应 s 的「e d b f a c」。一开始谁也不连谁,每个索引自己是一组,所以右边连通分量个数是 6。接下来按 pairs 一对一对地连。
待处理的索引对 · [0,2] [2,4] [1,5]：这道例子的 pairs 有三对:[0,2]、[2,4]、[1,5]。也就是要把索引 0 和 2、2 和 4、1 和 5 分别连起来。索引 3 一次都没出现,等会儿它会一直孤零零。一对一对处理。
第 0 对 · 连 0 与 2：看第 0 对 [0,2]:位置 0 和位置 2 可以互换。先紫色点亮这两个索引,准备把它们并成一组。
找代表元 · 0→0, 2→2：合并前各自找代表元,也就是树根。现在 0 的根是 0、2 的根是 2,都还是自己,谁也没被并过。根不同,可以合。
合并 · 0 指向 2：按参考解的写法,让 0 的根指向 2 的根,于是 0 挂到 2 下面,这一组成了 {0,2}。连通分量从 6 降到 5。
第 1 对 · 连 2 与 4：看第 1 对 [2,4]:位置 2 和位置 4 可换。注意 2 已经带着 0 是一组了,这一步会把整组接到 4 上,传递性就体现在这。先点亮 2 和 4。
找代表元 · 2→2, 4→4：找根:2 的根是 2、4 的根是 4,都是各自树根。真正要连的是这两个根。
合并 · 2 指向 4 · 0 也跟过来：让 2 的根指向 4。现在 0 → 2 → 4 串成一棵树,根是 4,这一组变成 {0,2,4}。从没直接说 0 和 4 能换,但通过 2 这个中间人,它们被传递地连到了一起。连通分量降到 4。
第 2 对 · 连 1 与 5：看第 2 对 [1,5]:位置 1 和位置 5 可换。它们和左边那棵树没关系,是另一组。点亮 1 和 5。
找代表元 · 1→1, 5→5：找根:1 的根是 1、5 的根是 5,都还独立。根不同,可以合。
合并 · 1 指向 5：让 1 的根指向 5,这一组成了 {1,5}。现在场上有两棵树外加孤立的 3,一共 3 个连通分量。
分组定型 · {0,2,4} · {1,5} · {3}：三对全处理完,索引分成三组:{0,2,4} 一组、{1,5} 一组、索引 3 自己一组。每组内部的字符都可以自由重排,而 3 谁也连不上,它那位字符只能原地不动。下面切到字符串,逐组排序填回。
把 s 平铺成一排:索引 0 到 5 上是 e、d、b、f、a、c。现在三组的归属已经定了,我们一组一组来,先看最左边的那棵大树 {0,2,4}。
绿色点亮 {0,2,4} 这一组,把它们位置上的字符抓出来看:索引 0 是 e、索引 2 是 b、索引 4 是 a,凑成 e、b、a 三个字符。因为它们连通,这三个字符能在这三个位置上任意摆放。
把这三个字符按字典序排好:a ≤ b ≤ e。再把这一组的索引也从小到大列出来:0、2、4。接下来让最小的 a 进最小的索引 0,次小的 b 进 2,最大的 e 进 4。
把 a 写进索引 0。这是组内最小的字符,落到组内最小的位置。此刻整串是 adbfac。
把 b 写进索引 2。次小的接着放到次小的位置。此刻整串是 adbfac。
把 e 写进索引 4。组内最后一个,最大的 e 落到最大的索引 4,这一组排完了。此刻整串是 adbfec。
换第二组 {1,5}。蓝色那三位是已经排好的 {0,2,4},别再动它们。绿色点亮 1 和 5,取出字符:索引 1 是 d、索引 5 是 c,凑成 d、c。
排一下:c ≤ d。索引从小到大是 1、5。于是 c 进索引 1、d 进索引 5。原来 1 是 d、5 是 c,正好对调一下。
把 c 写进索引 1。小的 c 进小的索引 1。现在整串是 acbfec。
把 d 写进索引 5。剩下的 d 进索引 5,这一组也排完了。现在整串是 acbfed。
最后是孤零零的索引 3。它没和任何位置配过对,所属的组只有它自己,字符 f 没有任何挪动空间,只能原地保持。所以第 3 位还是 f。
六个位置全部落定:{0,2,4} 排成 a、b、e,{1,5} 排成 c、d,f 守在第 3 位。从左到右读出来就是 acbfed。每组都让小字符占了小位置,逐位都尽量小,整串就是字典序最小。
边界先想清:没有对子就原样返回;连成一整组就是把这组字符整体排序填回。
两个高频追问:可用连通分量替代并查集;填回时两个升序对齐就不会错。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(s) p = list(range(n)) for a, b in pairs: p[find(a)] = find(b) d = defaultdict(list) for i, c in enumerate(s): d[find(i)].append(c) for i in d.keys(): d[i].sort(reverse=True) return "".join(d[find(i)].pop() for i in range(n))复杂度
- 时间：O((n+m)·α + n·log n)，n 是串长、m 是 pairs 个数;m 次合并、n 次查根近似线性,各组字符总量是 n,排序合计 O(n·log n)
- 空间：O(n)，parent 数组长 n,加上按组存放字符也是 n,峰值与串长同阶
易错点
面试追问把动画讲成自己的话
追问不用并查集能做吗?
追问每组排序填回,顺序会不会搞反?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计封闭岛屿的数目
LeetCode 1254 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题