1
class DSU:
2
    def __init__(self):
3
        self.parentof = [-1 for _ in range(100001)]
4
        self.rankof = [1 for _ in range(100001)]
5

6
    def find(self, ele):
7
        def recur(ele):
8
            if self.parentof[ele] == -1:
9
                return ele
10
            par = recur(self.parentof[ele])
11
            self.parentof[ele] = par
12
            return par
13

14
        return recur(ele)
15

16
    def unify(self, ele1, ele2):
17
        p1, p2 = self.find(ele1), self.find(ele2)
18
        r1, r2 = self.rankof[p1], self.rankof[p2]
19

20
        if p1 == p2:
21
            return
22
        if r1 > r2:
23
            self.parentof[p2] = p1
24
        else:
25
            self.parentof[p1] = p2
26
            if r1 == r2:
27
                self.rankof[p2] += 1
28

29

30
class Solution:
31
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
32
        dsu = DSU()
33
        nodes = set()
34
        smallest = [s[i] for i in range(len(s))]
35

36
        for i, j in pairs:
37
            dsu.unify(i, j)
38
            nodes.add(i)
39
            nodes.add(j)
40

41
        groups = {}
42
        for node in nodes:
43
            par = dsu.find(node)
44
            if par not in groups:
45
                groups[par] = [node]
46
            else:
47
                groups[par].append(node)
48

49
        for group in groups.values():
50
            letters, k = sorted([s[i] for i in group]), 0
51

52
            for i in group:
53
                smallest[i] = letters[k]
54
                k += 1
55

56
        return "".join(smallest)