#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++

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)

Explanation

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.

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#

1using System;
2using System.Collections.Generic;
3using System.Linq;
4
public class Solution {
    public string SmallestStringWithSwaps(string s, IList<IList<int>> pairs) {
        int n = s.Length;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        foreach (var pair in pairs) {
            graph[pair[0]].Add(pair[1]);
            graph[pair[1]].Add(pair[0]);
        }

        bool[] visited = new bool[n];
        char[] result = s.ToCharArray();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                var indices = new List<int>();
                var chars = new List<char>();
                DFS(i, graph, visited, indices, chars, result);
                indices.Sort();
                chars.Sort();
                for (int j = 0; j < indices.Count; j++) {
                    result[indices[j]] = chars[j];
                }
            }
        }
        return new string(result);
    }

    private void DFS(int node, List<int>[] graph, bool[] visited, List<int> indices, List<char> chars, char[] result) {
        visited[node] = true;
        indices.Add(node);
        chars.Add(result[node]);
        foreach (int neighbor in graph[node]) {
            if (!visited[neighbor]) {
                DFS(neighbor, graph, visited, indices, chars, result);
            }
        }
    }
}