# Leetcode 1308 Solution

This article provides solution to leetcode question 1308 (smallest-string-with-swaps)

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)
``````