![https://leetcode.com/problems/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.
1
2
3
4
5
6
7
| 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"
|
1
2
3
4
5
6
7
8
| 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"
|
1
2
3
4
5
6
7
8
| 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| class Solution {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int n = s.length();
UF uf = new UF(n);
for (int i = 0; i < pairs.size(); i++) {
List<Integer> pair = pairs.get(i);
uf.union(pair.get(0), pair.get(1));
}
Map<Integer, List<Character>> idToChars = new HashMap<>();
for (int i = 0; i < n; i++) {
int id = uf.find(i);
List<Character> chars = idToChars.getOrDefault(id, new ArrayList<>());
chars.add(s.charAt(i));
idToChars.put(id, chars);
}
for (Integer id: idToChars.keySet()) {
List<Character> chars = idToChars.get(id);
Collections.sort(chars);
idToChars.put(id, chars);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int id = uf.find(i);
sb.append(idToChars.get(id).remove(0));
}
return sb.toString();
}
public class UF {
int[] a;
int[] sz;
public UF(int n) {
this.a = new int[n];
this.sz = new int[n];
for (int i = 0; i < n; i++) {
a[i] = i;
sz[i] = 1;
}
}
void union(int p, int q) {
int pid = find(p);
int qid = find(q);
if (pid == qid) {
return;
}
if (sz[pid] >= sz[qid]) {
a[qid] = pid;
sz[pid] += sz[qid];
} else {
a[pid] = qid;
sz[qid] += sz[pid];
}
}
int find(int p) {
while (p != a[p]) {
p = a[p];
}
return p;
}
}
}
|