## Algorithm

Problem Name: 1061. Lexicographically Smallest Equivalent String

You are given two strings of the same length `s1` and `s2` and a string `baseStr`.

We say `s1[i]` and `s2[i]` are equivalent characters.

• For example, if `s1 = "abc"` and `s2 = "cde"`, then we have `'a' == 'c'`, `'b' == 'd'`, and `'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 `s1 = "abc"` and `s2 = "cde"`, `"acd"` and `"aab"` are equivalent strings of `baseStr = "eed"`, and `"aab"` is the lexicographically smallest equivalent string of `baseStr`.

Return the lexicographically smallest equivalent string of `baseStr` by using the equivalency information from `s1` and `s2`.

Example 1:

```Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, 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.
```

Example 2:

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

Example 3:

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

Constraints:

• `1 <= s1.length, s2.length, baseStr <= 1000`
• `s1.length == s2.length`
• `s1`, `s2`, and `baseStr` consist of lowercase English letters.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String smallestEquivalentString(String s1, String s2, String baseStr) {
int[] graph = new int[26];
for (int i = 0; i < 26; i++) {
graph[i] = i;
}
for (int i = 0; i < s1.length(); i++) {
int idxOne = s1.charAt(i) - 'a';
int idxTwo = s2.charAt(i) - 'a';
int parentOne = find(graph, idxOne);
int parentTwo = find(graph, idxTwo);
if(parentOne < parentTwo) {
graph[parentTwo] = parentOne;
} else {
graph[parentOne] = parentTwo;
}
}
StringBuilder sb = new StringBuilder();
for (char c : baseStr.toCharArray()) {
sb.append((char) ('a' + find(graph, c - 'a')));
}
return sb.toString();
}

private int find(int[] graph, int idx) {
while(graph[idx] != idx) {
idx = graph[idx];
}
return idx;
}
}
``````
Copy The Code &

Input

cmd
s1 = "parker", s2 = "morris", baseStr = "parser"

Output

cmd
"makkek"

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
var smallestEquivalentString = function (s1, s2, baseStr) {
if (s1.length === 0 || s2.length === 0) return ''
const uf = new UnionFind()
for (let i = 0; i < s1.length; i++) {
uf.union(s1[i], s2[i])
}
let res = ''
for (const ch of baseStr) {
res += uf.find(ch) || ch // some letters don't have connected component
}
return res
}
class UnionFind {
constructor() {
this.parents = new Map()
}
find(x) {
if (this.parents.get(x) === x) return x
this.parents.set(x, this.find(this.parents.get(x))) // path compression
return this.parents.get(x)
}
union(u, v) {
// init
if (!this.parents.has(u)) {
this.parents.set(u, u)
}
if (!this.parents.has(v)) {
this.parents.set(v, v)
}
// find root
const rootU = this.find(u)
const rootV = this.find(v)
if (rootU === rootV) return // connected already
// set smallest lex as the root
if (rootU > rootV) {
this.parents.set(rootU, rootV)
} else {
this.parents.set(rootV, rootU)
}
}
}
``````
Copy The Code &

Input

cmd
s1 = "parker", s2 = "morris", baseStr = "parser"

Output

cmd
"makkek"

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
def root(c):
return c if parent[c] == c else root(parent[c])
parent = {s: s for s in string.ascii_lowercase}
for a, b in zip(A, B):
p1, p2 = root(a), root(b)
if p1 <= p2:
parent[p2] = p1
else:
parent[p1] = p2
return ''.join(root(s) for s in S)
``````
Copy The Code &

Input

cmd
s1 = "hello", s2 = "world", baseStr = "hold"

Output

cmd
"hdld"

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Text;

namespace LeetCode
{
public class _1061_LexicographicallySmallestEquivalentString
{
public string SmallestEquivalentString(string A, string B, string S)
{
var uf = new UnionFind(26);
for (int i = 0; i < A.Length; i++)
uf.Union(A[i] - 'a', B[i] - 'a');

var sb = new StringBuilder(S.Length);
foreach (var ch in S)
sb.Append((char)(uf.Find(ch - 'a') + 'a'));

return sb.ToString();
}

private class UnionFind
{

public UnionFind(int count)
{
this.parents = new int[count];
for (int i = 0; i < count; i++)
parents[i] = i;
}

public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);
return parents[index];
}

public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);

if (pIndex1 == pIndex2) return;
if (pIndex1 < pIndex2)
parents[pIndex2] = pIndex1;
else
parents[pIndex1] = pIndex2;
}
}
}
}
``````
Copy The Code &

Input

cmd
s1 = "hello", s2 = "world", baseStr = "hold"

Output

cmd
"hdld"