1061. Lexicographically Smallest Equivalent String

Given strings `A` and `B` of the same length, we say A[i] and B[i] are equivalent characters. For example, if `A = "abc"` and `B = "cde"`, then we have `'a' == 'c', 'b' == 'd', 'c' == 'e'`.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: 'a' == 'a'
• Symmetry: 'a' == 'b' implies 'b' == 'a'
• Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'

For example, given the equivalency information from `A` and `B` above, `S = "eed"`, `"acd"`, and `"aab"` are equivalent strings, and `"aab"` is the lexicographically smallest equivalent string of `S`.

Return the lexicographically smallest equivalent string of `S` by using the equivalency information from `A` and `B`.

Example 1:

```Input: A = "parker", B = "morris", S = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in `A` and `B`, we can group their characters as `[m,p]`, `[a,o]`, `[k,r,s]`, `[e,i]`. The characters in each group are equivalent and sorted in lexicographical order. So the answer is `"makkek"`.
```

Example 2:

```Input: A = "hello", B = "world", S = "hold"
Output: "hdld"
Explanation:  Based on the equivalency information in `A` and `B`, we can group their characters as `[h,w]`, `[d,e,o]`, `[l,r]`. So only the second letter `'o'` in `S` is changed to `'d'`, the answer is `"hdld"`.
```

Example 3:

```Input: A = "leetcode", B = "programs", S = "sourcecode"
Explanation:  We group the equivalent characters in `A` and `B` as `[a,o,e,r,s,c]`, `[l,p]`, `[g,t]` and `[d,m]`, thus all letters in `S` except `'u'` and `'d'` are transformed to `'a'`, the answer is `"aauaaaaada"`.
```

Note:

1. String `A`, `B` and `S` consist of only lowercase English letters from `'a'` - `'z'`.
2. The lengths of string `A`, `B` and `S` are between `1` and `1000`.
3. String `A` and `B` are of the same length.

1061. Lexicographically Smallest Equivalent String
``````struct Solution;

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 {
j
} else {
self.parent[i] = self.find(j);
self.parent[i]
}
}

fn union(&mut self, mut i: usize, mut j: usize) {
i = self.find(i);
j = self.find(j);
if i != j {
let min = i.min(j);
self.parent[i] = min;
self.parent[j] = min;
}
}
}

impl Solution {
fn smallest_equivalent_string(a: String, b: String, s: String) -> String {
let a: Vec<usize> = a.bytes().map(|b| (b - b'a') as usize).collect();
let b: Vec<usize> = b.bytes().map(|b| (b - b'a') as usize).collect();
let n = a.len();
let mut uf = UnionFind::new(26);
for i in 0..n {
uf.union(a[i], b[i]);
}
s.bytes()
.map(|c| (uf.find((c - b'a') as usize) as u8 + b'a') as char)
.collect()
}
}

#[test]
fn test() {
let a = "parker".to_string();
let b = "morris".to_string();
let s = "parser".to_string();
let res = "makkek".to_string();
assert_eq!(Solution::smallest_equivalent_string(a, b, s), res);
let a = "hello".to_string();
let b = "world".to_string();
let s = "hold".to_string();
let res = "hdld".to_string();
assert_eq!(Solution::smallest_equivalent_string(a, b, s), res);
let a = "leetcode".to_string();
let b = "programs".to_string();
let s = "sourcecode".to_string();