1202. Smallest String With Swaps

题目信息

题号:

1202

难度:

Medium

主题:

字符串、并查集、连通分量、字典序

原题:

LeetCode 1202

重点:

pairs 中允许的交换可重复执行,因此同一连通分量内的字符可以任意重排;返回所有可达字符串中字典序最小者

题目重述

给定字符串 s 和下标对数组 pairs。对于每个 [a, b],可以交换 s[a] 与 s[b],并且任意允许的交换都可以执行任意多次、采用任意顺序。

间接连通的下标也能通过多次交换重新排列字符。请返回经过若干次合法交换后能够得到的字典序最小字符串;不要求实际输出交换步骤。

1 <= s.length <= 10^5,0 <= pairs.length <= 10^5;s 只包含小写英文字母,且每个下标对均位于字符串范围内。

自建示例

连通分量中的字符可以整体排序:

输入:s = "cba", pairs = [[0,1],[1,2]]
输出:"abc"
解释:三个下标彼此连通,因此字符 c、b、a 可以任意重排,字典序最小结果为 abc。

没有允许交换时字符串保持不变:

输入:s = "zxy", pairs = []
输出:"zxy"
解释:不存在合法交换,唯一可达字符串就是原字符串。