C# - UnionFind - Clean, Explained, Beats 100%
Intuition\nGoal is to replace baseStr\'s characters with the smallest character of set. Set is built by rules in problem description.\nSets are merging as we go
# Intuition\nGoal is to replace baseStr\'s characters with the smallest character of set. Set is built by rules in problem description.\nSets are merging as we go through strings.\nFinding unions from sets is known to be done with UnionFind algorithm.\n\n# Approach\nIf different characters - Union them.\nWhile at it, make the root of Union the smallest value (it is the min of existing set, so have to compare to another minimum (root) in Union).\nIn the end get each character\'s set root and build result.\n\n# Complexity\n- Time complexity:\nO(n + m) - going through s1, s2 (length n) + baseStr (length m)\n Finding root is always less then 26 hops = constant.\n\n- Space complexity:\nO(m) - building modified baseStr.\nBesides that UnionFind structure uses constant space from 26 english characters.\n\n# Code\n```\npublic class Solution {\n    private static readonly IReadOnlyList<char> EnglishLetters = Enumerable\n        .Range(0, 26)\n        .Select(code => Convert.ToChar(code + \'a\'))\n        .ToList();\n    \n    public string SmallestEquivalentString(string s1, string s2, string baseStr)\n    {\n        var uf = new UnionFind();\n        \n        for (int i = 0; i < s1.Length; i++)\n        {\n            uf.Union(s1[i], s2[i]);\n        }\n\n        var minimums = EnglishLetters\n            .ToDictionary(c => c, uf.Find);\n        var res = new StringBuilder();\n        \n        foreach (var c in baseStr)\n        {\n            res.Append(minimums[c]);\n        }\n\n        return res.ToString();\n    }\n    \n    public class UnionFind\n    {\n        public readonly Dictionary<char, char> parent =\n            EnglishLetters.ToDictionary(c => c, c => c);\n\n        public char Find(char a)\n        {\n            if (a == parent[a])\n            {\n                return a;\n            }\n\n            // optimize the path\n            return parent[a] = Find(parent[a]);\n        }\n\n        public void Union(char a, char b)\n        {\n            a = Find(a);\n            b = Find(b);\n\n            if (a == b) return;\n            \n            if (a < b)\n            {\n                parent[b] = a;\n            }\n            else\n            {\n                parent[a] = b;\n            }\n        }\n    }\n}\n```
['Union Find', 'C#']