Explained : Java | Union Find and Brute Force | Faster than 100%
\nWe represent the problem as a graph problem. Each group of characters represents a connected component. To solve this use Union Find to group the characters a
\nWe represent the problem as a graph problem. Each group of characters represents a connected component. To solve this use Union Find to group the characters and chose the lexicographically smallest member of each set to be the set\'s representative.\n\n##### Approach \nImplement Union Find. Unite all `s1[i]` and `s2[i]` for all `0 <= i < n.` Then iterate through the characters of baseStr and replace each with the **smallest representative** of its the group.\n\n#### Code\n\n```\nclass Solution \n{\n    public String smallestEquivalentString(String s1, String s2, String baseStr) \n    {\n        int[] graph = new int[26];\n        for(int i = 0; i < 26; i++) \n            graph[i] = i;\n            \n        for(int i = 0; i < s1.length(); i++) \n        {\n            int first = s1.charAt(i) - \'a\';\n            int second = s2.charAt(i) - \'a\';\n            int end1 = find(graph, first);\n            int end2 = find(graph, second);\n            if(end1 < end2) \n            {\n                graph[end2] = end1;\n            } \n            else \n            {\n                graph[end1] = end2;\n            }\n        }\n        StringBuilder sb = new StringBuilder();\n        for(int i = 0; i < baseStr.length(); i++) \n        {\n            char c = baseStr.charAt(i);\n            sb.append((char)(\'a\' + find(graph, c - \'a\')));\n        }\n        return sb.toString();\n    }\n    \n    private int find(int[] graph, int index) \n    {\n        while(graph[index] != index) \n        {\n            index = graph[index];\n        }\n        return index;\n    }\n}\n```\n\n##### Another solution (helpes in visualisation of set formation)\n*More like a brute force*\n```\nclass Solution {\n    public String smallestEquivalentString(String s1, String s2, String baseStr) \n    {\n        int len = s1.length();\n        List<Set<Character>> set = new ArrayList<>();\n        int currSet = 1;\n        int[] sets = new int[26];\n        for(int i=0; i<len; i++)\n        {\n            // System.out.println(set);\n            char c1 = s1.charAt(i);\n            char c2 = s2.charAt(i);\n            if(c1==c2) continue;\n            if(sets[c1-\'a\'] == 0 && sets[c2-\'a\'] == 0)\n            {\n                Set<Character> newSet = new TreeSet<>();\n                newSet.add(c1);\n                newSet.add(c2);\n                sets[c1-\'a\'] = currSet;\n                sets[c2-\'a\'] = currSet;\n                currSet++;\n                set.add(newSet);\n            }\n            else if(sets[c1-\'a\'] == 0)\n            {\n                Set<Character> curr = set.get(sets[c2-\'a\']-1);\n                curr.add(c1);\n                sets[c1-\'a\'] = sets[c2-\'a\'];\n            }\n            else if(sets[c2-\'a\'] == 0)\n            {\n                Set<Character> curr = set.get(sets[c1-\'a\']-1);\n                curr.add(c2);\n                sets[c2-\'a\'] = sets[c1-\'a\'];\n            }\n            else if(sets[c2-\'a\'] != sets[c1-\'a\'])\n            {\n                // System.out.println(Arrays.toString(sets));\n                // System.out.println(c2+"  "+c1);\n                Set<Character> first = set.get(sets[c1-\'a\']-1);\n                Set<Character> second = set.get(sets[c2-\'a\']-1);\n                for(char cha : second)\n                {\n                    first.add(cha);\n                    sets[cha-\'a\'] = sets[c1-\'a\'];\n                }\n                second.clear();\n            }\n        }\n        System.out.println(set);\n        \n        String ans = "";\n        for(int i=0; i<baseStr.length(); i++)\n        {\n            char ch = baseStr.charAt(i);\n            int index = sets[ch-\'a\']-1;\n            if(index<0) ans += ch;\n            else ans += set.get(index).iterator().next();;\n        }\n        return ans;\n        \n    }\n}\n```
['Java']