#1202 Smallest String With Swaps - Solution

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.

The key idea in #1202 Smallest String With Swaps is to recognize that the swap pairs form connected components in a graph. If two indices are connected directly or indirectly, their characters can be rearranged freely among those positions. This observation transforms the problem into grouping indices and then constructing the lexicographically smallest arrangement within each group.

You can model the problem using Union-Find (Disjoint Set Union) or graph traversal techniques like DFS/BFS. First, connect all indices given in pairs to identify components. For each component, collect the characters belonging to those indices, sort them, and then place the smallest characters back into the sorted index positions to achieve the minimal lexicographic result.

Union-Find is typically preferred because it efficiently merges and finds connected components. After grouping indices, sorting characters within each component ensures the final string is as small as possible. The main costs come from union operations and sorting within components.

Approach	Time Complexity	Space Complexity
Union-Find (Disjoint Set Union)	O(n log n + p α(n))	O(n)
DFS/BFS Connected Components	O(n log n + p)	O(n + p)

Solutions (4)

Union-Find (Disjoint Set Union)

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:

Initialize a Union-Find structure for the indices of the string.
Iterate through each pair in the 'pairs' array and perform union operations on the indices.
Create a mapping from root parent to all indices in that connected component by leveraging the 'find' operation.
For each component of indices, gather and sort the characters, then place them back in the original string positions according to indices mapping.

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.

Python C++

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}

Explanation

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.

DFS for Connected Components

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:

Build an adjacency list for the graph using the pairs provided.
For each index not yet visited, perform a DFS to discover all connected components.
Gather all indices in a connected component, sort the characters corresponding to these indices, and re-position them in the string.

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.

Java C#