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.
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5
6class UnionFind {
7public:
8 std::vector<int> parent;
9 UnionFind(int size) : parent(size) {
10 for (int i = 0; i < size; ++i) parent[i] = i;
11 }
12
13 int find(int x) {
14 if (x != parent[x]) {
15 parent[x] = find(parent[x]);
16 }
17 return parent[x];
18 }
19
20 void union_sets(int x, int y) {
21 int rootX = find(x);
22 int rootY = find(y);
23 if (rootX != rootY) {
24 parent[rootY] = rootX;
25 }
26 }
27};
28
29std::string smallestStringWithSwaps(std::string s, std::vector<std::vector<int>>& pairs) {
30 int n = s.size();
31 UnionFind uf(n);
32 for (auto& p : pairs) {
33 uf.union_sets(p[0], p[1]);
34 }
35 std::unordered_map<int, std::vector<int>> groups;
36 for (int i = 0; i < n; ++i) {
37 groups[uf.find(i)].emplace_back(i);
38 }
39 for (auto& [_, indices] : groups) {
40 std::string t = "";
41 for (int index : indices) {
42 t += s[index];
43 }
44 std::sort(t.begin(), t.end());
45 for (size_t i = 0; i < indices.size(); ++i) {
46 s[indices[i]] = t[i];
47 }
48 }
49 return s;
50}The C++ solution similarly uses Union-Find to track connected groups of indices, leveraging unordered maps to store groups of indices with their corresponding root parent. The characters in each of these index groups are sorted and reassigned in their original positions to form the final string.
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.