Leetcode 1308 Solution

class FindUnionSet:
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, i):
        if i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])
        return self.parents[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:
            self.parents[root_i] = root_j

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        fuset = FindUnionSet(len(s))
        for i, j in pairs:
            fuset.union(i, j)

        groups = collections.defaultdict(list)
        for i in range(len(s)):
            root_i = fuset.find(i)
            groups[root_i].append(i)

        sorted_substrs = []
        for ids in groups.values():
            sorted_substrs.append((
                ids, sorted([s[i] for i in ids])
            ))

        ans = [None] * len(s)
        for ids, chars in sorted_substrs:
            for i, ch in zip(ids, chars):
                ans[i] = ch

        return "".join(ans)