DSU Solution (CPP) beat 100% ✅
Intuition\nWe want to make a components with characters and get the minimum of each component\n\n# Approach\n- Reflexivity: \'a\' == \'a\'.\n- Symmetry: \'a\' =
# Intuition\nWe want to make a components with characters and get the minimum of each component\n\n# Approach\n- **Reflexivity:** `\'a\' == \'a\'`.\n- **Symmetry:** `\'a\' == \'b\' implies \'b\' == \'a\'`.\n- **Transitivity:** `\'a\' == \'b\' and \'b\' == \'c\' implies \'a\' == \'c\'`.\nthat means if there are two equivalent characters so the equivalent characters of the two characters are equivalent.\n\n***We will use Disjoint Set Union ( [DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html) )***\n\n# Complexity\n- Time complexity:\n    - $O(N \\times log(26))$ $\\approx$ $O(5 \\times N)$ $\\approx$ $O(N)$ \n        - Where $N$ is the number of characters in the strings\n\n- Space complexity:\n    - $O(26)$ $\\approx$ $O(1)$\n# Code\n```\ntemplate < typename T = int, int Base = 0 > struct DSU {\n    \n    vector < T > parent;\n\n    // every parent will be a char equal to it, 0 -> \'a\', 1 -> \'b\' and so on\n    DSU(int MaxNodes){\n        parent = vector < T > (MaxNodes + 5);\n        for(int i = Base; i <= MaxNodes; i++)\n          parent[i] = char(i + \'a\');\n    }\n\n    // git the index of the char to acces the vector\n    int fix(char c){\n        return c - \'a\';\n    }\n\n    // get the leader of each component\n    T find_leader(char node){\n        return parent[fix(node)] = (parent[fix(node)] == node ? node : find_leader(parent[fix(node)]));\n    }\n\n    // check if the two chars in the same set\n    bool is_same_sets(char u, char v){\n        return find_leader(u) == find_leader(v);\n    }\n\n    // union two component together and make the leader is the smallest character in the component\n    void union_sets(char u, char v){\n        char leader_u = find_leader(u), leader_v = find_leader(v);\n        if(leader_u == leader_v) return;\n        if(leader_u > leader_v) \n            swap(leader_u, leader_v);\n        parent[fix(leader_v)] = leader_u;\n    }\n\n    // get the minimum character in component and it is the leader of the component\n    char get_min(char c){\n        return find_leader(c);\n    }\n};\n\nclass Solution {\npublic:\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        // DSU with char type\n        DSU < char > dsu(26);\n        \n        // number of character\n        int n = s1.size();\n\n        // union the two sets of the two characters together\n        for(int i = 0; i < n; i++)\n            dsu.union_sets(s1[i], s2[i]);\n\n        // replace every char in baseStr with the minimum char of it\'s set\n        for(auto& c : baseStr)\n            c = dsu.get_min(c);\n\n        // the minimum lexicographically baseStr\n        return baseStr;      \n    }\n};\n```\n\n![2ddedd60-39d6-4167-9b77-88e10400f044_1673586388.8794823.jpeg](https://assets.leetcode.com/users/images/e72a5c55-b314-4ec6-9229-fb73b8eb7f55_1673697700.0906572.jpeg)\n
['Tree', 'Union Find', 'Graph', 'C++']