## Algorithm

Problem Name: 1202. Smallest String With Swaps

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.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String smallestStringWithSwaps(String s, List pair : pairs) {
disjointSet.union(pair.get(0), pair.get(1));
}
Map();
for (int i = 0; i  <  n; i++) {
int root = disjointSet.find(i);
map.computeIfAbsent(root, k -> new PriorityQueue < >()).offer(s.charAt(i));
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i  <  s.length(); i++) {
sb.append(map.get(disjointSet.find(i)).poll());
}
return sb.toString();
}

private static final class DisjointSet {

private final int[] root;
private final int[] rank;
public int unionCount;

public DisjointSet(int size) {
this.root = new int[size];
this.rank = new int[size];
for (int i = 0; i  <  size; i++) {
this.root[i] = i;
this.rank[i] = 1;
}
this.unionCount = size;
}

public void union(int nodeOne, int nodeTwo) {
int rootOne = find(nodeOne);
int rootTwo = find(nodeTwo);
if (rootOne != rootTwo) {
if (this.rank[rootOne] > this.rank[rootTwo]) {
this.root[rootTwo] = rootOne;
} else if (this.rank[rootOne]  <  this.rank[rootTwo]) {
this.root[rootOne] = rootTwo;
} else {
this.root[rootTwo] = rootOne;
this.rank[rootOne]++;
}
this.unionCount--;
}
}

public int find(int node) {
if (node == root[node]) {
return node;
}
return root[node] = find(root[node]);
}
}
}
``````
Copy The Code &

Input

cmd
s = "dcab", pairs = [[0,3],[1,2]]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const smallestStringWithSwaps = function(s, pairs) {
let set = Array(s.length).fill(-1)
function union(a, b) {
let root1 = find(a)
let root2 = find(b)
if (root1 !== root2) {
set[root2] = root1
}
}
function find(a) {
if (set[a] < 0) {
return a
} else {
return (set[a] = find(set[a]))
}
}
for (let pair of pairs) {
union(pair[0], pair[1])
}
let groups = []
for (let i = 0; i  <  s.length; i++) {
groups[i] = []
}
for (let i = 0; i  <  s.length; i++) {
groups[find(i)].push(i)
}
let sArr = s.split('')
for (let i = 0; i  <  s.length; i++) {
if (groups[i].length > 1) {
let chars = groups[i].map(idx => s[idx])
chars.sort()
for (let k = 0; k  <  groups[i].length; k++) {
sArr[groups[i][k]] = chars[k]
}
}
}
return sArr.join('')
}
``````
Copy The Code &

Input

cmd
s = "dcab", pairs = [[0,3],[1,2]]

Output

cmd
"bacd"

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
class UF:
def __init__(self, n): self.p = list(range(n))
def union(self, x, y): self.p[self.find(x)] = self.find(y)
def find(self, x):
if x != self.p[x]: self.p[x] = self.find(self.p[x])
return self.p[x]
uf, res, m = UF(len(s)), [], collections.defaultdict(list)
for x,y in pairs:
uf.union(x,y)
for i in range(len(s)):
m[uf.find(i)].append(s[i])
for comp_id in m.keys():
m[comp_id].sort(reverse=True)
for i in range(len(s)):
res.append(m[uf.find(i)].pop())
return ''.join(res)
``````
Copy The Code &

Input

cmd
s = "dcab", pairs = [[0,3],[1,2],[0,2]]

Output

cmd
"abcd"