Leetcode 1202. Smallest String With Swaps

Problem Explanation

The problem involves a given string and an array of indices pair. We are allowed to swap characters at given indices in the pair array. Our goal is to use any number of swaps and return the lexicographically smallest string possible.

For example: Given the string s = "dcab" and the pair array pairs = [[0,3],[1,2]]. We can reach the smallest possible string by swapping characters at index 0 and 3 resulting in a string s = "bcad". Then we swap characters at index 1 and 2 getting the string s = "bacd".

The problem uses the concept of Union-Find data structure to solve the problem efficiently given the large constraints.

Solution Approach

The solution arranges the array indices into disjoint sets using the Union-Find data structure. After finding the disjoint sets, we pick all indices of the same disjoint set and arrange letters at those indices so that the resulting string is lexicographically smallest.

This is achieved by mapping each disjoint set to a heap, in which all characters of the same disjoint set are stored. For a string s and its corresponding disjoint set, the character with the highest priority (smallest character since it's a min-heap) in the heap of the set is the next character in the resultant string.

For example:

Given the string s = "dcab" and the pair array pairs = [[0,3],[1,2],[0,2]].

After swapping character at index 0 with 3, we get the string s = "bcad".

After swapping character at index 0 with 2, we get the string s = "acbd".

After swapping character at index 1 with 2, we get the string s = "abcd".

Here is the implementation of this solution in C++, Java, Python, and JavaScript languages:

C++ Solution

1
2C++
3class UnionFind {
4 public:
5  UnionFind(int n) : id(n), rank(n) {
6    iota(begin(id), end(id), 0);
7  }
8
9  void unionByRank(int u, int v) {
10    const int i = find(u);
11    const int j = find(v);
12    if (i == j)
13      return;
14    if (rank[i] < rank[j]) {
15      id[i] = id[j];
16    } else if (rank[i] > rank[j]) {
17      id[j] = id[i];
18    } else {
19      id[i] = id[j];
20      ++rank[j];
21    }
22  }
23
24  int find(int u) {
25    return id[u] == u ? u : id[u] = find(id[u]);
26  }
27   private:
28  vector<int> id;
29  vector<int> rank;
30};
31
32class Solution {
33 public:
34  string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
35    string ans;
36    UnionFind uf(s.length());
37    unordered_map<int, priority_queue<char, vector<char>, greater<>>> map;
38
39    for (const vector<int>& pair : pairs)
40      uf.unionByRank(pair[0], pair[1]);
41
42    for (int i = 0; i < s.length(); ++i)
43      map[uf.find(i)].push(s[i]);
44
45    for (int i = 0; i < s.length(); ++i)
46      ans += map[uf.find(i)].top(), map[uf.find(i)].pop();
47
48    return ans;
49  }
50};

Java Solution

1
2java
3class Solution {
4  private int[] parent;
5
6  public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
7    if (pairs.size() == 0) {
8      return s;
9    }
10
11    int len = s.length();
12    this.parent = new int[len];
13    for (int i = 0; i < len; i++) {
14      parent[i] = i;
15    }
16
17    for (List<Integer> pair : pairs) {
18      union(pair.get(0), pair.get(1));
19    }
20
21    char[] charArray = s.toCharArray();
22    Map<Integer, PriorityQueue<Character>> hashMap = new HashMap<>(len);
23    for (int i = 0; i < len; i++) {
24      int root = find(i);
25      if (hashMap.containsKey(root)) {
26        hashMap.get(root).offer(charArray[i]);
27      } else {
28        PriorityQueue<Character> minHeap = new PriorityQueue<>();
29        minHeap.offer(charArray[i]);
30        hashMap.put(root, minHeap);
31      }
32    }
33    
34    StringBuilder stringBuilder = new StringBuilder();
35    for (int i = 0; i < len; i++) {
36      int root = find(i);
37      stringBuilder.append(hashMap.get(root).poll());
38    }
39
40    return stringBuilder.toString();
41  }
42
43  private void union(int index1, int index2) {
44    int root1 = find(index1);
45    int root2 = find(index2);
46    if (root1 == root2) {
47      return;
48    }
49    parent[root1] = root2;
50  }
51
52  private int find(int index) {
53    if (index != parent[index]) {
54      parent[index] = find(parent[index]);
55    }
56    return parent[index];
57  }
58}

Python Solution

1
2python
3class UF:
4    def __init__(self, n):
5        self.parent = list(range(n))
6        self.size = [1] * n
7
8    def find(self, x):
9        if x != self.parent[x]:
10            self.parent[x] = self.find(self.parent[x])
11        return self.parent[x]
12
13    def union(self, x, y):
14        p, q = self.find(x), self.find(y)
15        if p == q:
16            return
17        if self.size[p] < self.size[q]:
18            self.parent[p] = q
19            self.size[q] += self.size[p]
20        else:
21            self.parent[q] = p
22            self.size[p] += self.size[q]
23
24class Solution:
25    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
26        uf = UF(len(s))
27        for x, y in pairs:
28            uf.union(x, y)
29        d = collections.defaultdict(list)
30        for i in range(len(s)):
31            d[uf.find(i)].append(s[i])
32        for k in d:
33            d[k].sort(reverse=True)
34        ans = list()
35        for i in range(len(s)):
36            ans.append(d[uf.find(i)].pop())
37        return "".join(ans)

JavaScript Solution

1
2javascript
3var smallestStringWithSwaps = function(s, pairs) {
4    let parent = []
5    for(let i = 0; i < s.length; i++) parent[i] = i // initialize parent array
6	let find = (index) => {
7		if (parent[index] != index){
8			parent[index] = find(parent[index]) // path compression
9		}
10		return parent[index]
11    }
12	let union = (index1, index2) => {
13        let parent1 = find(index1), parent2 = find(index2)
14		if(parent1 != parent2) parent[parent1] = parent2 // put them in the same group
15    }
16	
17    for(let pair of pairs) union(pair[0], pair[1]) // union operation for each pair
18
19    let group = [], res = []
20    for(let i = 0; i < s.length; i++){
21        let index = find(i) // find father index for each character
22        if(!group[index]) group[index] = []
23		group[index].push(s[i]) // group characters by their disjoint set id
24    }
25	
26    for(let arr of group)
27        if(arr) arr.sort((a, b) => a < b ? 1 : -1) // lex order for each group of chars
28	
29    for(let i=0; i<s.length; i++){
30        let index = find(i) // father index
31		res.push(group[index].pop()) // .pop() already gives us lex smallest, since we sorted in descending order
32    }
33   
34    return res.join('')
35};

Solution in Detail

The primary logic behind the problem’s solution derives from the functioning of Disjoint Sets, here represented through UnionFind class in Java, JavaScript and C++, and UF class in Python. These classes are used to group the indices together in the form of disjoint sets. The underlying principle here is to emphasize grouping more than comparison between elements, therefore, the Union and Find functions are widely used.

After the UnionFind object is initialized, pairs of indices are unionised to bring them into a common set. This ensures that, at the end of this step, a common parent node is assigned to all related indices, creating multiple disjoint sets.

Next, we iterate through the entire string to establish a heap of characters where each disjoint set is represented by a heap of its related characters. The point to note here is that in the Java and JavaScript implementations, the heap is created as a priority queue, automatically sorting its elements in ascending lexicographical order, while in the Python implementation, we manually sort and reverse the elements for later convenience in popping off the smallest elements.

Finally, iterating through the string once more, we find the set corresponding to each index, then pop off and append the smallest character from that set heap, replacing it in the output string.

Time Complexity Analysis

The time complexity of this solution can be summarised as O(nlogn), where n is the length of the string. In Python, additional logn is spent on sorting the characters, but it does not change the larger time complexity since it is still dominated by the nlogn operations related to heap management. The solution performs well even for strings as large as 10^5 characters, given this efficient time complexity.

Alternative Solutions

An alternative solution could use other data structures like an array of lists or a dictionary of lists, where each list contains the indices of the related characters in the same order as they appear in the string. This approach may work perfectly for a small string size, but its performance drastically decreases for larger strings as it results in a time complexity of O(n^2). Thus, the solution using the Union-Find data structure is the most efficient one. The usage of heap data structure ensures the efficient extraction of smallest character at each step, therefore providing the lexicographically smallest string as the output.

This solution can be implemented in multiple programming languages using the same underlying logic, by making appropriate changes according to the syntax of each language. The Python solution, for example, is very neat and straightforward due to Python's inbuilt libraries and flexible syntax, while equivalent implementations in other languages like C++ and Java may seem a bit verbose due to limitations in their syntax, particularly around collection types. JavaScript's dynamic nature provides an implementation somewhere in between these.