A novelty font draws some letters identically. You receive two strings a and b of equal length: for every index i, the letters a[i] and b[i] look alike. Looking alike is reflexive, symmetric and transitive: every letter looks like itself, and if x looks like y and y looks like z, then x looks like z.
Given a string word, replace every letter by the alphabetically smallest letter that looks like it, and return the result. Letters of word that are not mentioned in a or b stay unchanged.
Examples
Input: a = "dog", b = "cat", word = "good"
Output: "gaac"
Explanation: the classes are {c, d}, {a, o} and {g, t}.
Input: a = "abc", b = "bcd", word = "dad"
Output: "aaa"
Input: a = "zy", b = "yx", word = "zzz"
Output: "xxx"
Constraints
0 <= len(a) = len(b) <= 10**4,0 <= len(word) <= 10**4, lowercase letters only- Target: O((len(a) + len(word)) * alpha(26)) time.
Goals
- Build equivalence classes of letters from paired strings
- Keep the smallest member as each class's representative