1202. Smallest String With Swaps - cocoder39/coco39_LC GitHub Wiki

1202. Smallest String With Swaps

same as 1722. Minimize Hamming Distance After Swap Operations

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        def find(i):
            while i != parent[i]:
                parent[i] = parent[parent[i]]
                i = parent[i]
            return i
        
        def union(i, j):
            root_i, root_j = find(i), find(j)
            if root_i != root_j:
                if size[root_i] > size[root_j]:
                    parent[root_j] = root_i;
                    size[root_i] += size[root_j]
                else:
                    parent[root_i] = root_j;
                    size[root_j] += size[root_i]
        
        n = len(s)
        parent = [i for i in range(n)]
        size = [1] * n
        for i, j in pairs:
            union(i, j)
        
        mp = collections.defaultdict(list)
        for i, ch in enumerate(s):
            root = find(i)
            mp[root].append(ch)
        
        for key, value in mp.items():
            value.sort(reverse = True)
        
        res = []
        for i in range(n):
            root = find(i)
            res.append(mp[root].pop())
        return ''.join(res)