✅✅Efficient C++ DSU Solution With Explanation
116 / 116 test cases passed\nStatus: Accepted\nRuntime: 0 ms\nMemory Usage: 6.6 MB\n\n\nBasic Intuition\n\n The rules for the "equivalent characters" introduced
**116 / 116** test cases passed\nStatus: **Accepted**\nRuntime: *0 ms*\nMemory Usage: *6.6 MB*\n\n\n***Basic Intuition***\n\n* The rules for the "equivalent characters" introduced in the problem simply means the two characters are belong to the same group.\n* And our job is that for each character in baseStr, we need to find its belonging group and find the smallest character from that group.\n* So we have two tasks:\n* Create all the groups with equivalent characters from s1 and s2.\n--> Find the group each character in baseStr, and find the smallest character in that group\n--> Grouping connected elements can be done using DFS/BFS/Union-find.\n\n***Efficient C++ Solution*** : \n```\nclass Solution {\nprivate:\n    //Parent vector for storing parents. It stores lexicographically smallest equivalent of a character. For ex, if the equivalent of s->r, r->o ; the parent of both s and r becomes o simultaneously by DSU path compression.\n    vector<int> par;\n    \n    //Path Compression\n    int find(int u){\n        return par[u]==-1 ? u : par[u]=find(par[u]);\n    }\n    \n    //Merge the components\n    //If parent of both nodes is same, backtrack and if not, then map the largest character to the smallest one by Path compression...\n    void Union(int u,int v){\n        u=find(u), v=find(v);\n        if(u != v)\n            par[max(u, v)] = min(u, v);\n    }\npublic:\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        int n=s1.size();\n        \n        //Initially parent of all nodes is -1\n        par.assign(26, -1);\n        \n        \n        //Merging the nodes\n        for(int i=0; i<n; ++i)\n            Union(s1[i]-\'a\', s2[i]-\'a\');\n        \n        \n        //Mapping largest char with the smallest one. If no mapping is there, or no node for an element is found in the DSU map, we will write the character as it is, as it\'s parent will be -1.  \n        for(char& c: baseStr)\n            c = find(c-\'a\')+\'a\';\n        \n        return baseStr;    //Return the final answer :)\n    }\n};\n```
['Union Find']