Solution Using DSU and DFS with Intuition
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nwhat do u want as ans ... the lexicographically minimum string how can achieve 
![qmjl5kfi4cyc1.gif](https://assets.leetcode.com/users/images/e0ef5686-33bb-40e8-9dee-e87abc25c82e_1720157227.171041.gif)\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwhat do u want as ans ... the lexicographically minimum string how can achieve this ..can be achieved by getting the minimum for each characters of the baseStr right? basic u know how to make the graph out of the two strings by the it will be a undirected graph each in this way u will be able to find the ans.\n\nNow The Intuition for the Approachs :-\n\n\n------------------------------------Intuition for DFS ------------------------------------\nInitially every characters of baseStr treats themselves as minimum b/c they only know this much right they don\'t their connections/or about adjaceny .. Now u made a Graph so you about your connections \nthen u will go and find out in your connection are ur value is lesser than me and that one ask for its ... neighbors  and so on so... Until u visited all the neighbours .. and if u find the smaller character  than urself then u will replace ....Now check out the dfs Code for more clarification.\n\n\n\n------------------------------------Intuition for DSU ------------------------------------\n\nHow to do Guess that this is a DSU problem ..for me its always the leader i am leader of the clan where in the question i smell this leader thing it\'s most of the time a dsu problem ...here Clan refers as component  and in this question clan can be referred  as the characters of the baseStr..B/c Initially members/Characters of baseStr know that i am the leader/ minimum of the all ....\nNow what u do u merge the Components right in dsu to know who is going to be the leader of this component/smallest so we will merge one by one s1[i] and s2[i] ... and simply for each of the characters of the baseStr find their leader/smallest/minimum  and replace it with the actual one .\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nFor DFS:-\n\nO(n)->for craeting adj list the length of the s1 \nO(26 * 26)=>O(V+E) :- we can only have 26 charcters not more than that\nmeans O(26) per DFS call \nO(26.m)=>since each DFS take O(26) :-  O(26) * the length baseStr i.e. O(26 * m);\n\nHance overall O(n+26 * m +26 * 26) hence O(n+m);\n\n\nFor DSU:- \nO(26) :-for find and Union intialization,\nO(n* factor) :- taken by Union operation ,n- lengthh of s1|s2 and factor some path compression factor for Union which takes alpha(n) time.\nO(m*factor) :- taken for the finding the rank of each of teh baseStr characters,m-lengtb of teh baseStr\n\nSo overall Tc will be :- O(n)+ O(n*factor) + O(m*factor) Hence O(n+m)\n\n\n![GI2jhU9.gif](https://assets.leetcode.com/users/images/c5d6e05b-9ca1-4fd9-ab3d-debdf50fce86_1720157154.5887966.gif)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\n// AB ITNA LIKHA HAI TO UPVOTE TO KAR HI DENA PLZ\n\nclass Solution {\npublic:\n    // Using Dsu\n\n    vector<int> rank;\n    vector<int> parent;\n    int find(int x){\n        if(parent[x]==x) return x;\n        return parent[x]=find(parent[x]);\n    }\n    void Union(int x,int y){\n        int X=find(x);\n        int Y=find(y);\n        if(X!=Y){\n            if(X < Y) parent[Y]=X;\n            else  parent[X]=Y;\n        }\n    }\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        int n=s1.size();\n        rank.resize(26,0);\n        parent.resize(26);\n        for(int i=0;i<26;i++){\n            parent[i]=i;\n        }\n        for(int i=0;i<n;i++){\n            Union(s1[i]-\'a\',s2[i]-\'a\');\n        }\n        for(auto &ch :baseStr){\n            ch=find(ch-\'a\')+\'a\';\n        }\n        return baseStr;\n    }\n};\n```\n```\n/// Lo bhaiya DFS wala bhi le lo\n\nclass Solution {\npublic:\n    void dfs(int node, vector<bool>& visited, vector<vector<int>>& adj, char& minChar, string& labels) {\n        visited[node] = true;\n        minChar = min(minChar, labels[node]);\n        for (int neighbor : adj[node]) {\n            if (!visited[neighbor]) {\n                dfs(neighbor, visited, adj, minChar, labels);\n            }\n        }\n    }\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        vector<vector<int>> adj(26);\n        int n = s1.size();\n        for (int i = 0; i < n; i++) {\n            int ch1 = s1[i] - \'a\';\n            int ch2 = s2[i] - \'a\';\n            adj[ch1].push_back(ch2);\n            adj[ch2].push_back(ch1);\n        }\n\n        string labels = "abcdefghijklmnopqrstuvwxyz";\n        for (char& ch : baseStr) {\n            vector<bool> visited(26, false);\n            char minChar = ch;\n            dfs(ch - \'a\', visited, adj, minChar, labels);\n            ch = minChar;\n        }\n\n        return baseStr;\n    }\n};\n```\nHappy Coding\uD83D\uDE0A\n![MuaKissGIF.gif](https://assets.leetcode.com/users/images/3f579146-ba01-4c34-9791-9af73731fd5a_1720157375.5632923.gif)\n
['String', 'Depth-First Search', 'Union Find', 'C++']