C++ || Union Find
The equal characters can thought to be connected with one another.We will be thinking of this problem as a graph problem where the equal characters are connecte
The equal characters can thought to be connected with one another.We will be thinking of this problem as a graph problem where the equal characters are connected to each other. In the final string we will be finding the lexographically smallest alphabet available in the component of the current character and add it to the answer.\nThis problem can also be done using dfs since there is no restriction about the properties changing midway.\n\n```cpp\nclass Solution {\n    struct DSU\n    {\n        vector<int> siz,parent;\n        void init()\n        {\n            siz.resize(26);\n            parent.resize(26);\n            for(int i=0;i<26;i++)\n            {\n                siz[i]=1;\n                parent[i]=i;\n            }\n        }\n        int leader(int ex)\n        {\n            if(ex==parent[ex])\n                return ex;\n            return parent[ex]=leader(parent[ex]);\n        }\n        void merge(int a,int b)\n        {\n            a=leader(a);\n            b=leader(b);\n            if(a==b)\n                return;\n            if(siz[a]<siz[b])\n                swap(a,b);\n            siz[a]+=siz[b];\n            parent[b]=parent[a];\n        }\n    };\npublic:\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        DSU d;\n        d.init();\n        for(int i=0;i<s1.size();i++)\n            d.merge(s1[i]-\'a\',s2[i]-\'a\');\n        vector<char> represent(26,\'z\');\n        for(int i=0;i<26;i++)\n            represent[d.leader(i)]=std::min(represent[d.leader(i)],(char)(\'a\'+i));\n        string ans="";\n        for(auto ele : baseStr)\n            ans+=represent[d.leader(ele-\'a\')];\n        return ans;\n    }\n};\n```
['Union Find', 'C']