Sponsored
Sponsored
In this approach, we use the Union-Find (also known as Disjoint Set Union, DSU) data structure. This structure helps efficiently group indices that can be swapped. Once we group the indices, we can individually sort characters in each connected component to ensure the smallest lexicographical order.
Steps:
Time Complexity: O(M * α(N) + NlogN), where M is the number of pairs, α is the inverse Ackermann function (very small constant), and N is the length of the string.
Space Complexity: O(N) for the union-find structure and the character groups.
1class UnionFind:
2 def __init__(self, size):
3 self.parent = list(range(size))
4
5 def find(self, x):
6 if self.parent[x] != x:
7 self.parent[x] = self.find(self.parent[x])
8 return self.parent[x]
9
10 def union(self, x, y):
11 rootX = self.find(x)
12 rootY = self.find(y)
13 if rootX != rootY:
14 self.parent[rootY] = rootX
15
16def smallestStringWithSwaps(s, pairs):
17 if not s:
18 return ""
19 n = len(s)
20 uf = UnionFind(n)
21 for x, y in pairs:
22 uf.union(x, y)
23
24 import collections
25 groups = collections.defaultdict(list)
26 for i in range(n):
27 root = uf.find(i)
28 groups[root].append(i)
29
30 res = list(s)
31 for indices in groups.values():
32 sorted_chars = sorted(res[i] for i in indices)
33 for i, char in zip(sorted(indices), sorted_chars):
34 res[i] = char
35 return ''.join(res)The provided Python code defines a UnionFind class to help manage connected components through union and find operations. The 'smallestStringWithSwaps' function makes use of this class to find connected components from the given pairs. For each component, it sorts the characters and places them back in the string res according to their indices.
This approach utilizes Depth-First Search (DFS) to find connected components in a graph that represents swap pairs. Each unique character component is individually sorted to form the smallest possible string.
Steps:
Time Complexity: O(N + M + C log C), where N is the number of nodes, M is the number of edges in the graph (pairs), and C is the size of the largest component.
Space Complexity: O(N + M), as we store the adjacency graph and visit flags.
1import java.util.*;
The Java solution uses an adjacency list to represent the swap pairs as a graph. It performs a DFS from each unvisited node to discover all nodes connected to it, gathering indices and corresponding characters. These gathered components are sorted to ensure lexicographically smallest entries at their respective indices.