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^50 <= pairs.length <= 10^50 <= pairs[i][0], pairs[i][1] < s.lengthsonly 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]);
}
}
}
Input
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('')
}
Input
s = "dcab", pairs = [[0,3],[1,2]]
Output
"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)
Input
s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output
"abcd"