Lexicographically Smallest Equivalent String | 100% faster | Easy Explanation
Intuition\nFrom the problem statement it is clear that the graph will be disconnected. Each component of the graph will contain equivalent characters to each ot
# Intuition\nFrom the problem statement it is clear that the graph will be disconnected. Each component of the graph will contain equivalent characters to each other. In order to derive the lexicographically smallest equivalent string of baseStr, we need to find the lexicographic smallest character in that particular component where baseStr[j] exist.\n\n# Approach\n- Initialize parent array of size=26 (a-->z) as -1.\n\n- Traverse strings s1 and string s2 and connect s1[i] to s2[i]. To connect first find the ultimate parent(lexicographically smallest character in particular component) of both the characters using find_par(). Make the lexicographic smaller character as parent of the bigger lexicographic character.\n\n- Traverse the baseStr and replace baseStr[j] with the lexicographic smallest equivalent character (i.e., ultimate parent of baseStr[j]).\n\n# Complexity\n- Time complexity:\n    $$O(n+m)k$$\n\n        make_union() and find_par() takes constant time (say k).\n        n==s1.size()==s2.size()\n        m==baseStr.size()\n\n- Space complexity:\n$$O(1)$$\n\n\n# Code\n```\nclass Solution {\npublic:\n\n    int find_par(int node,vector<int>&parent){\n        if(parent[node]==-1)\n        return node;\n\n        return parent[node]=find_par(parent[node],parent);  //returns ultimate parent\n    }\n\n    void  make_union (int u, int v, vector<int>&parent){\n        u=find_par(u,parent);\n        v=find_par(v,parent);\n\n        //connect lexicographically\n        if(u<v)\n        parent[v]=u;\n            \n        else if(u>v)\n        parent[u]=v;\n            \n        }\n\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n\n        vector<int>parent(26,-1); //intialize the parent array\n        \n        for(int i=0; i<s1.size(); i++){\n            if(s1[i]!=s2[i])\n            make_union(s1[i]-\'a\',s2[i]-\'a\',parent);  //connect the correspoding equivalent characters\n        }\n\n        for(int j=0; j<baseStr.size(); j++){\n            baseStr[j]=find_par(baseStr[j]-\'a\',parent)+\'a\';\n        }\n\n        return baseStr;\n\n    }\n};\n```
['String', 'Union Find', 'C++']