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.
Rust Solution
struct Solution;
use std::cmp::Reverse;
use std::collections::HashMap;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
i
} else {
let k = self.find(j);
self.parent[i] = k;
k
}
}
fn union(&mut self, mut i: usize, mut j: usize) {
i = self.find(i);
j = self.find(j);
if i != j {
self.parent[i] = j;
}
}
}
impl Solution {
fn smallest_string_with_swaps(s: String, pairs: Vec<Vec<i32>>) -> String {
let n = s.len();
let mut uf = UnionFind::new(n);
let mut hm: HashMap<usize, Vec<char>> = HashMap::new();
for pair in pairs {
uf.union(pair[0] as usize, pair[1] as usize);
}
for (i, c) in s.char_indices() {
hm.entry(uf.find(i)).or_default().push(c);
}
for v in hm.values_mut() {
v.sort_unstable_by_key(|&x| Reverse(x));
}
let mut res: Vec<char> = vec![];
for i in 0..n {
res.push(hm.entry(uf.find(i)).or_default().pop().unwrap());
}
res.into_iter().collect()
}
}
#[test]
fn test() {
let s = "dcab".to_string();
let pairs = vec_vec_i32![[0, 3], [1, 2]];
let res = "bacd".to_string();
assert_eq!(Solution::smallest_string_with_swaps(s, pairs), res);
let s = "dcab".to_string();
let pairs = vec_vec_i32![[0, 3], [1, 2], [0, 2]];
let res = "abcd".to_string();
assert_eq!(Solution::smallest_string_with_swaps(s, pairs), res);
let s = "cba".to_string();
let pairs = vec_vec_i32![[0, 1], [1, 2]];
let res = "abc".to_string();
assert_eq!(Solution::smallest_string_with_swaps(s, pairs), res);
}
Having problems with this solution? Click here to submit an issue on github.