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.

1202. Smallest String With Swaps
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);
}