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 pairsany 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.
Solutions
Solution 1: Union-Find
We notice that the index pairs have transitivity, i.e., if $a$ and $b$ can be swapped, and $b$ and $c$ can be swapped, then $a$ and $c$ can also be swapped. Therefore, we can consider using a union-find data structure to maintain the connectivity of these index pairs, and sort the characters belonging to the same connected component in lexicographical order.
Finally, we traverse the string. For the character at the current position, we replace it with the smallest character in the connected component, then remove this character from the connected component, and continue to traverse the string.
The time complexity is $O(n \times \log n + m \times \alpha(m))$, and the space complexity is $O(n)$. Here, $n$ and $m$ are the length of the string and the number of index pairs, respectively, and $\alpha$ is the inverse Ackermann function.
implSolution{#[allow(dead_code)]pubfnsmallest_string_with_swaps(s:String,pairs:Vec<Vec<i32>>)->String{letn=s.as_bytes().len();lets=s.as_bytes();letmutdisjoint_set:Vec<usize>=vec![0;n];letmutstr_vec:Vec<Vec<u8>>=vec![Vec::new();n];letmutret_str=String::new();// Initialize the disjoint setforiin0..n{disjoint_set[i]=i;}// Union the pairsforpairinpairs{Self::union(pair[0]asusize,pair[1]asusize,&mutdisjoint_set);}// Initialize the return vectorfor(i,c)ins.iter().enumerate(){letp_c=Self::find(i,&mutdisjoint_set);str_vec[p_c].push(*c);}// Sort the return vector in reverse orderforcur_vecin&mutstr_vec{cur_vec.sort();cur_vec.reverse();}// Construct the return stringforiin0..n{letindex=Self::find(i,&mutdisjoint_set);ret_str.push(str_vec[index].last().unwrap().clone()aschar);str_vec[index].pop();}ret_str}#[allow(dead_code)]fnfind(x:usize,d_set:&mutVec<usize>)->usize{ifd_set[x]!=x{d_set[x]=Self::find(d_set[x],d_set);}d_set[x]}#[allow(dead_code)]fnunion(x:usize,y:usize,d_set:&mutVec<usize>){letp_x=Self::find(x,d_set);letp_y=Self::find(y,d_set);d_set[p_x]=p_y;}}