1202

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


        parents = [i for i in range(N)]
        size = [1 for i in range(N)]

        def find(i: int) -> None:
            root = i
            while root != parents[root]:
                root = parents[root]

            while parents[i] != root:
                t = parents[i]
                parents[i] = root
                i = t

            return root

        def union(i: int, j: int) -> None:
            i = find(i)
            j = find(j)

            if i == j:
                return

            if size[i] < size[j]:
                j, i = i, j

            parents[j] = i
            size[i] += size[j]

        for i, j in pairs:
            union(i, j)

        letter_sets = defaultdict(set)
        for i in range(N):
            p = find(i)
            letter_sets[p].add(i)

        ans = list(s)
        for letter_set in letter_sets.values():
            letters = [s[i] for i in letter_set]
            letters.sort()
            for idx, i in enumerate(sorted(letter_set)):
                ans[i] = letters[idx]

        return "".join(ans)