[C++] Find&Union solution | Explained | TC: O(n) | SC: O(n)
Intuition\nFor each letter c we want to know what is the best letter, that we can turn it into by using the legal operations. Find&Union will allow us to answer
# Intuition\nFor each letter `c` we want to know what is the best letter, that we can turn it into by using the legal operations. Find&Union will allow us to answer that question fast and to update our structure in a blink of an eye.\n\n# Approach\nFirstly we write the standard Find&Union functions. Because we are talking about `char` variables we substract `\'a\'` to access the real value.\n\nThen we iterate though the strings `s1` and `s2` and update the values using F&U funcitons. \n\nLastly we generate the answer :D\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    char find_fast(char x, char fu[26]) {\n        if (fu[x - \'a\'] != x)\n            fu[x - \'a\'] = find_fast(fu[x - \'a\'], fu);\n\n        return fu[x - \'a\'];\n    }\n\n    void union_fast(char x, char y, char fu[26]) {\n        fu[find_fast(x, fu) - \'a\'] = find_fast(y, fu);\n    }\n\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        int n = s1.size();\n\n        char fu[26];\n        for (int i = 0; i < 26; i++)\n            fu[i] = \'a\' + i;\n\n        for (int i = 0; i < n; i++) {\n            char c1 = find_fast(s1[i], fu);\n            char c2 = find_fast(s2[i], fu);\n\n            if (c1 != c2) {\n                if (c1 < c2)\n                    swap(c1, c2);\n                union_fast(c1, c2, fu);\n            }\n        }\n\n        string ans = "";\n        for (auto c : baseStr)\n            ans += find_fast(c, fu);\n        return ans;\n    }\n};\n```
['Union Find', 'C++']