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.

class Solution {
    int g[26];
    int find(int n) {
        return g[n] == n ? n : g[n] = find(g[n]);
    }
    void uni(int a, int b) {
        int pa = find(a), pb = find(b);
        g[pa] = g[pb] = min(pa, pb);
    }
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        for(int i = 0; i < 26; i++) g[i] = i;
        for(int i = 0; i < s1.length(); i++) {
            uni(s1[i] - 'a', s2[i] - 'a');
        }
        for(int i = 0; i < baseStr.length(); i++) {
            baseStr[i] = 'a' + find(baseStr[i]-'a');
        }
        return baseStr;
    }
};