1202. Smallest String With Swaps¶
题目信息¶
- 题号:
1202
- 难度:
Medium
- 主题:
字符串、并查集、连通分量、字典序
- 原题:
- 重点:
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"
解释:不存在合法交换,唯一可达字符串就是原字符串。