1202. Smallest String With Swaps

Smallest String With Swaps - LeetCode

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1: Input: s = “dcab”, pairs = [[0,3],[1,2]] Output: “bacd” Explaination: Swap s[0] and s[3], s = “bcad” Swap s[1] and s[2], s = “bacd” Example 2: Input: s = “dcab”, pairs = [[0,3],[1,2],[0,2]] Output: “abcd” Explaination: Swap s[0] and s[3], s = “bcad” Swap s[0] and s[2], s = “acbd” Swap s[1] and s[2], s = “abcd” Example 3: Input: s = “cba”, pairs = [[0,1],[1,2]] Output: “abc” Explaination: Swap s[0] and s[1], s = “bca” Swap s[1] and s[2], s = “bac” Swap s[0] and s[1], s = “abc”

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

  • code
class UF:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.rank = [1] * n
    
    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]
    
    def union(self, x, y):
        rtx = self.find(x)
        rty = self.find(y)
        if rtx == rty: return
        rkx = self.rank[x]
        rky = self.rank[y]
        if rkx < rky:
            self.root[rtx] = rty
        elif rkx > rky:
            self.root[rty] = rtx
        else:
            self.root[rtx] = rty
            self.rank[rty] += 1

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        uf = UF(len(s))
        for px, py in pairs:
            uf.union(px, py)
        groups = defaultdict(list)
        for i in range(len(s)):
            groups[uf.find(i)].append(i)
        
        res = [""] * len(s)
        for k, group in groups.items():
            chars = [s[i] for i in group]
            chars.sort()
            for i in range(len(chars)):
                res[group[i]] = chars[i]
                
        return "".join(res)