Find smallest string
·
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.
class UnionFind:
def __init__(self, n):
self.size = n
self.parent = [i for i in range(n)]
def find(self, u):
if u != self.parent[u]:
self.parent[u] = self.find(self.parent[u]) # Path compression
return self.parent[u]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv: return False
self.parent[pu] = pv
return True
def getGroups(self):
groups = defaultdict(list)
for u in range(self.size):
groups[self.find(u)].append(u)
return groups.values()
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
n, m = len(s), len(pairs)
uf = UnionFind(n)
for u, v in pairs:
uf.union(u, v)
groups = uf.getGroups()
res = ['-'] * n
for group in groups:
chars = [s[i] for i in group]
chars.sort()
group.sort()
for i, c in zip(group, chars):
res[i] = c
return "".join(res)
Link:: Leetcode Detailed Graph