[C++][JAVA]| Detailed Explanation w/ TWO METHODS | COMMENTED CODE WITH EXAMPLES
METHOD 1 (DFS):\n\nIntuition:\n Problem is looking for the lexicographically smallest equivalent string of baseStr by using equivalency information of strings s
***METHOD 1 (DFS):***\n\n**Intuition:**\n* Problem is looking for the lexicographically smallest equivalent string of baseStr by using equivalency information of strings s1 and s2.\n* So if we observe then we will found out that we have to ***make some connection*** between characters of strings s1 and s2.\n\n* After establishing characters between them (means after making component) we can then pick the smallest character out of them \nand replace a specific character in baseStr with connected minimum character which we will found out in establishing connection.\n* Now, if we observe some terminology that we use in above statements as (e.g connection between words) we found that we ***can represent every character as a node*** \nand then ***connection between them can be called as edge between those characters***.\n* So, whole problem can be treated as **graph problem** and to each character (now called as a node)\nwe will create a connection with equivalency information provided to us (now called as an edge).\n_______\n**WHAT WE WILL DO:**\n* We will divide the question in three parts:\n* Make the adjacency List from the given string s1 and s2 with the condition of equivalence relation. \n      i) One thing that we have to notice here is that index 0 will represent character \u2018a\u2019 , index 1 will represent character \u2018b\u2019, index 2 will represent character \u2018c\u2019 and so on\u2026.\n* We will replace each character (i.e from \u2018a\u2019 to \u2018z\u2019) with minimumm character we will found out in that component.\n\n* Now we will replace the character of baseStr with the minimum character we wil found out in the component of that character.\n\n**SOME NOTES:**\n* Our visited vector will be work as to find out that a character is already visited or not as well as the minimum character we found out for each character in their respective component.\n* Since, we are playing here with  characters, so we will declare our visited vector of size 26 only, coz English alphabets have 26 characters only.\n_________\n**Time and Space Complexity:**\n```\nTime Complexity: O(n), because we will establish connection according to given equivalence relation.\nSpace Complexity: O(n), we will make adjacency list here.\n```\n_____\n**CODES:**\n* **C++**\n```\nclass Solution {\npublic:\n    void dfs(vector<char> adj[], char node, char minCharacter, vector<char>& visited)\n    {\n        // to this character, replace it with it\'s minimum character\n        visited[node - \'a\'] = minCharacter;\n        \n        // travel in neighbour of this character,\n        // i.e travel in component of this character\n        for(char& near: adj[node - \'a\'])\n        {\n            // if this character is not visited, call dfs for it\n            if(visited[near - \'a\'] == \'#\')\n            {\n                dfs(adj, near, minCharacter, visited);\n            }\n        }\n    }\n    \n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        int n = s1.size(); // extract size\n        \n        vector<char> adj[26]; // declaring adjacency matrix\n        \n        // travel through strings and establish connection\n        for(int i = 0; i < n; i++)\n        {\n            adj[s1[i] - \'a\'].push_back(s2[i]);\n            adj[s2[i] - \'a\'].push_back(s1[i]);\n        }\n        \n        // make a visited vector of size 26\n        // and symbol, \'#\' denotes that this particular character is not visited yet\n        vector<char> visited(26, \'#\');\n        \n        // now, travel through each character\n        for(char c = \'a\'; c <= \'z\'; c++)\n        {\n            // if this character is not visited yet, call dfs here \n            if(visited[c - \'a\'] == \'#\')\n            {\n                // as we are calling dfs for each character, so\n                // it will minimum value for that component.\n                dfs(adj, c, c, visited);\n            }\n        }\n        \n        // Now lastly, replace each baseStr character with their \n        // minimum found out character in their component,\n        for(int i = 0; i < baseStr.size(); i++)\n        {\n            baseStr[i] = visited[baseStr[i] - \'a\'];\n        }\n        \n        // return baseStr now, \n        return baseStr;\n    }\n};\n```\n* **JAVA:**\n```\nclass Solution {\n    public void dfs(List<Character>[] adj, char node, char minCharacter, char [] visited)\n    {\n        // to this character, replace it with it\'s minimum character\n        visited[node - \'a\'] = minCharacter;\n        \n         // travel in neighbor of this character,\n        // i.e travel in component of this character\n        for(char near: adj[node - \'a\'])\n        {\n            // if this character is not visited, call dfs for it\n            if(visited[near - \'a\'] == \'#\')\n            {\n                dfs(adj, near, minCharacter, visited);\n            }\n        }\n    }\n    \n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        int n = s1.length(); // extract size\n        \n        List<Character>[] adj = new List[26]; // declaring adjacency matrix\n        for (int i = 0; i < 26; i++) \n        {\n            adj[i] = new ArrayList<>();\n        }\n        \n        // travel through strings and establish connection\n        for(int i = 0; i < n; i++)\n        {\n            adj[s1.charAt(i) - \'a\'].add(s2.charAt(i));\n            adj[s2.charAt(i) - \'a\'].add(s1.charAt(i));\n        }\n        \n        // make a visited vector of size 26\n        // and symbol,\'#\' denotes that this particular character is not visited yet\n        char [] visited = new char[26];\n        for(int i = 0; i < 26; i++)\n        {\n            visited[i] = \'#\';\n        }\n        \n         // now, travel through each character\n        for(char c = \'a\'; c <= \'z\'; c++)\n        {\n            // if this character is not visited yet, call dfs here \n            if(visited[c - \'a\'] == \'#\')\n            {\n                 // as we are calling dfs for each character, so\n                // it will minimum value for that component.\n                dfs(adj, c, c, visited);\n            }\n        }\n        \n        // Now lastly, replace each baseStr character with their \n        // minimum found out character in their component,\n        String ans = "";\n        for(int i = 0; i < baseStr.length(); i++)\n        {\n            ans += visited[baseStr.charAt(i) - \'a\'];\n        }\n        \n        // finally return ans string\n        return ans;\n    }\n}\n```\n_____________\n***METHOD 2 (DSU / UNION FIND) :***\n* Now, If we observe our above approach,\nwe will found out that between each character of s1 and s2, we are establishing connection and hence end up in making a whole component.\n* So can\u2019t we are able to group characters and then for each character we will simply see that which character is minimum in them.\n* Therefore, we will use DSU or say union find here.\n\n* Code template i used here is standard format.\n________\n**CODES:**\n* **C++**\n```\nclass Solution {\npublic:\n    char parent[26]; // make a parent array of size 26\n    \n    // find function used for finding parent of charter ch\n    char find(char ch)\n    {\n        // standard base condition of find function, \n        // at any point parent of this charcter equals to itself only return\n        if(parent[ch - \'a\'] == ch)\n            return ch;\n        \n        // else move on in finding parent\n        return parent[ch - \'a\'] = find(parent[ch - \'a\']);\n    }\n    \n    // Union function to merge parents of them\n    void Union(char first, char second)\n    {\n        // extract parent of both characters\n        char ParentOfFirst = find(first);\n        char ParentOfSecond = find(second);\n        \n        // whichever parent is less than other, \n        // make that parent\n        if(ParentOfFirst < ParentOfSecond)\n        {\n            parent[ParentOfSecond - \'a\'] = ParentOfFirst;\n        }\n        else\n        {\n            parent[ParentOfFirst - \'a\'] = ParentOfSecond;\n        }\n    }\n    \n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        int n = s1.size(); // extract size\n        \n        // Intially, all are the parents of themselves only\n        for(char c = \'a\'; c <= \'z\'; c++)\n        {\n            parent[c - \'a\'] = c;\n        }\n        \n        // now, apply Union function on s1 and s2\n        for(int i = 0; i < n; i++)\n        {\n            Union(s1[i], s2[i]);\n        }\n\n        // finally update baseStr\n        for(int i = 0; i < baseStr.size(); i++)\n        {\n            baseStr[i] = find(baseStr[i]);\n        }\n        \n        return baseStr;\n    }\n};\n```\n* **JAVA:**\n```\nclass Solution {\n    char [] parent = new char[26]; // make a parent array of size 26\n    \n     // find function used for finding parent of charter ch\n    public char find(char ch)\n    {\n        // standard base condition of find function, \n        // at any point parent of this character equals to itself only return\n        if(parent[ch - \'a\'] == ch)\n            return ch;\n        \n        // else move on in finding parent\n        return parent[ch - \'a\'] = find(parent[ch - \'a\']);\n    }\n    \n    // Union function to merge parents of them\n    public void Union(char first, char second)\n    {\n        // extract parent of both characters\n        char ParentOfFirst = find(first);\n        char ParentOfSecond = find(second);\n        \n        // whichever parent is less than other, \n        // make that parent\n        if(ParentOfFirst < ParentOfSecond)\n        {\n            parent[ParentOfSecond - \'a\'] = ParentOfFirst;\n        }\n        else\n        {\n            parent[ParentOfFirst - \'a\'] = ParentOfSecond;\n        }\n    }\n    \n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        int n = s1.length(); // extract size\n        \n        // Intially, all are the parents of themselves only\n        for(char c = \'a\'; c <= \'z\'; c++)\n        {\n            parent[c - \'a\'] = c;\n        }\n        \n        // now, apply Union function on s1 and s2\n        for(int i = 0; i < n; i++)\n        {\n            Union(s1.charAt(i), s2.charAt(i));\n        }\n        \n        // finally return ans;\n        String ans = "";\n        for(int i = 0; i < baseStr.length(); i++)\n        {\n            ans += find(baseStr.charAt(i));\n        }\n        \n        return ans;\n    }\n}\n```\n\n***`If u find this useful , please consider to give an upvote!!`***\n\n
['Union Find', 'C', 'Java']