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

## 1、题目描述¶

输入：s = "dcab", pairs = [[0,3],[1,2]]



输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]



输入：s = "cba", pairs = [[0,1],[1,2]]



• $1 <= s.length <= 10^5$
• $0 <= pairs.length <= 10^5$
• $0 <= pairs[i][0], pairs[i][1] < s.length$
• s 中只含有小写英文字母

## 2、解题思路¶

• 基本思路为将所有能够相关交换的位置的字母按照字典序排序，一次放入对应的位置中
• 使用并查集，将所有的能够联通的位置放到一个集合中，进行排序
from collections import defaultdict
from collections import deque

class DFU:
def __init__(self, length):
self.data = list(range(length))

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
self.data[xp] = yp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
length = len(s)
ans = [""] * length

d = DFU(length)
for x, y in pairs:
d.union(x, y)
change_pairs = defaultdict(list)

for i in range(length):
change_pairs[d.find(i)].append(s[i])

for key in change_pairs.keys():
change_pairs[key].sort(reverse=True)

for i in range(length):
ans[i] = change_pairs[d.find(i)].pop()
return "".join(ans)