Leetcode 1308 Solution

This article provides solution to leetcode question 1308 (smallest-string-with-swaps)
Categories:
Tags:
Access this page by simply typing in "lcs 1308" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/smallest-string-with-swaps

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)