JAVA | 3 solutions | With / without Union find, DFS✅
Please Upvote :D\n---\n##### 1. Using Union find algorithm:\nWe have used the typical Union find template.\njava []\n// Smallest Lexicographically Equivalent Le
# Please Upvote :D\n---\n##### 1. Using Union find algorithm:\nWe have used the typical Union find template.\n``` java []\n// Smallest Lexicographically Equivalent Letter = SLEL\nclass Solution {\n    private class UnionFind {\n        private int[] parentArr;    // stores the SLEL for all 26 characters\n        private UnionFind(int n) {\n            parentArr = new int[n]; // initialise the parent array\n            // // By default, each letter itself is it\'s SLEL\n            for (int i = 0; i < n; i++) {\n                parentArr[i] = i;\n            }\n        }\n\n        // this method would fetch us the SLEL for a particular character\n        private int getParent(int i) {\n            // example : SLEL of k is k, so we return k\n            // but SLEL of s is r, again we see SLEL of r is k \n            // (recursive call getParent(parentArr[i]) will keep setting SLELs of our character at index i) till we\n            // reach the situation "each letter itself is it\'s SLE" is encountered (parentArr[i] == i)\n            // character k has been set as the SLEL of r and s and we return k when k/r/s is passed\n            return (parentArr[i] == i)? i : (parentArr[i] = getParent(parentArr[i])); \n        }\n\n        // this method would set the SLELs for each corresponding characters in s1 and s2\n        private void union(int i, int j) {\n            int parent1 = getParent(i); // get the SLEL for char at index i\n            int parent2 = getParent(j); // get the SLEL for char at index i\n            if (parent1 < parent2) {    // if SLEL at i < SLEL at j\n                // SLEL at i now becomes SLEL at j too \n                parentArr[parent2] = parent1;   \n            } else {    // SLEL at i > SLEL at j\n                // SLEL at j now becomes SLEL at i too \n                parentArr[parent1] = parent2;   \n            }\n        }\n    }\n\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        UnionFind uf = new UnionFind(26);   // initialises our UnionFind object\n        for (int i = 0; i < s1.length(); i++) {\n            int c1 = s1.charAt(i) - \'a\';\n            int c2 = s2.charAt(i) - \'a\';\n            uf.union(c1, c2);   // this will map the SLEL to c1 as well as SLEL to c2 in the parent array\n        }\n\n        StringBuilder sb = new StringBuilder(); // to build our answer string\n        for (int i = 0; i < baseStr.length(); i++) {\n            // this would fetch us the SLEL for our current character of baseStr\n            int smallestMappedChar = uf.getParent(baseStr.charAt(i) - \'a\');\n            sb.append((char) (smallestMappedChar + \'a\'));   // we will append it to our answer\n        }\n\n        return sb.toString();   // return the answer string\n    }\n}\n\n// TC: O(len(s1) + len(baseStr)), SC: O(1)\n```\n---\n\n##### 2. Without using Union Find algorithm:\n*Inspired from the solution of **[YatharthVyas\n](https://leetcode.com/problems/lexicographically-smallest-equivalent-string/solutions/3047721/easy-c-solution-using-array-without-union-find/?orderBy=most_votes)***\n``` java []\nclass Solution {\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        // Smallest Lexicographically Equivalent Letter = SLEL\n        // creating an array of size 26 which will store the SLELs\n        char[] arr = new char[26];\n        // By default, each letter itself is it\'s SLEL\n        for (char c = \'a\'; c <= \'z\'; c++) {\n            arr[c - \'a\'] = c;\n        }\n\n        // Now we will iterate over the strings and map them to their SLELs\n        for (int i = 0; i < s1.length(); i++) {\n            char c1 = s1.charAt(i), c2 = s2.charAt(i);\n            // say we have characters \'p\' and \'m\' at same index of s1 and s2,\n            // out of both of them \'m\' is smaller, so it is SLEL for \'p\'\n            char toReplace = (char) Math.max(arr[c1-\'a\'], arr[c2-\'a\']);     // replace: max(\'p\', \'m\') = \'p\'\n            char replaceWith = (char) Math.min(arr[c1-\'a\'], arr[c2-\'a\']);   // with: min(\'p\', \'m\') = \'m\'\n            // we will wherever \'p\' is and put \'m\' in its place.\n            for (int j = 0; j < 26; j++) {\n                if (arr[j] == toReplace) {  // found \'p\'\n                    arr[j] = replaceWith;   // put \'m\'\n                }\n            }\n\n            // say for example we have \'k\' and \'r\', so we will put \'k\' in places of \'r\'s.\n            // then we get the pair \'r\' and \'s\', but in place of \'r\' we have already put \'k\' (arr[\'r\'] = \'k\')\n            // REPLACE : max(arr[\'r\'], arr[\'s\']) => max(\'k\', \'s\') => \'s\'\n            // WITH    : min(arr[\'r\'], arr[\'s\']) => min(\'k\', \'s\') => \'k\'\n            // So wherever \'s\' is in the array, we will put \'k\' in its place\n            // which means for \'s\', \'k\' is the SLEL\n        }\n\n        StringBuilder sb = new StringBuilder();     // create a stringbuilder to build our answer string\n        // We will append the SLEL for each character in baseStr\n        for (char c : baseStr.toCharArray()) {\n            sb.append(arr[c - \'a\']);\n        }\n\n        return sb.toString();   // return the answer string\n    }\n}\n\n// TC: O(n * 26) + O(m) => O(n + m)\n// n be the length of s1 and s2\n// m be the length of baseStr\n\n// SC: O(26) => O(1)\n```\n---\n##### 3. DFS approach:\n``` java []\nclass Solution {\n    private Map<Character, List<Character>> adj = new HashMap<>();  // globally initialise the adjacency map\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        // populate the adjacency map\n        for (int i = 0; i < s1.length(); i++) {\n            char c1 = s1.charAt(i);\n            char c2 = s2.charAt(i);\n            adj.putIfAbsent(c1, new ArrayList<>());\n            adj.putIfAbsent(c2, new ArrayList<>());\n            adj.get(c1).add(c2);\n            adj.get(c2).add(c1);\n        }\n\n        // Smallest Lexicographically Equivalent Letter = SLEL\n        StringBuilder sb = new StringBuilder();     // to store the answer string\n        for (char c : baseStr.toCharArray()) {\n            // we will perform a dfs and find the SLEL corresponding to each character in baseStr\n            // we also paa in a boolean visited array to avoid going back to same characters where we came from\n            char smallestChar = DFS(c, new boolean[26]);\n            sb.append(smallestChar);    // append the SLEL to the stringbuilder\n        }\n        \n        return sb.toString();       // return the answer string\n    }\n\n    private char DFS(char currChar, boolean[] visited) {\n        // since we have visited this letter (currChar), we mark it so we don\'t visit it again \n        visited[currChar - \'a\'] = true;    \n        // if the character is not in our adjacency list, means it wasn\'t present in s1 or s2\n        // So it itself is it\'s SLEL\n        if (!adj.containsKey(currChar)) {\n            return currChar;    // so we return currChar itself\n        }\n        \n        // now lets initialise our SLEL character variable with currChar\n        // we assume our character itself is it\'s SLEL\n        char smallestChar = currChar;\n        for (char childChar : adj.get(currChar)) {     // we look at all characters connected to current character\n            if (!visited[childChar - \'a\']) {           // if it wasn\'t visited already, we do some work\n                // since our currChar is connected to childChar, we will see what the SLEL for our childChar is\n                char smallestConnectedChar = DFS(childChar, visited);  // it will fetch us the SLEL for our childChar\n                // the SLEL for our currChar would be the smaller character between itself and the SLEL of child\n                smallestChar = (char) Math.min(smallestChar, smallestConnectedChar);\n            }\n        }\n\n        return smallestChar;    // we will return the SLEL (also it will be utilised during backtracking)\n    }\n}\n\n// TC: O(m * (v + e)), SC: O(v + e)\n```
['Depth-First Search', 'Union Find', 'Java']