JAVA | UFDS (w/ template) | Faster than 100 % |
Intuition\nThis is as straight forward of a DSU/UFDS problem as they come. One could think of equivalent characters as elements belonging to the same set. If a 
# Intuition\nThis is as straight forward of a DSU/UFDS problem as they come. One could think of equivalent characters as elements belonging to the same set. If a certain character of one set is found to be equivalent to be the character of some other set, a union of those two sets has to be performed. Also, the smallest character in each set has to be tracked so as to finally construct our answer.\n\n# Approach\nStart by initialsing a UFDS class with 26 elements (elements being the characters of a set). Take union of two equivalent characters a/c to String S1 and S2, while taking union, keep tracking the minimum element of the sets involved using an extra \'min\' array. To finally construct the answer, find the min character for each set a character of the baseStr String belongs to. \n\n\n# Code\n```\nclass Solution {\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        \n        UFDS dsu = new UFDS(26);\n        for(int i = 0; i < s1.length(); i++){\n            dsu.union(s1.charAt(i)-97,s2.charAt(i)-97);\n        }\n\n        StringBuilder sb = new StringBuilder(); \n\n        for(int i = 0; i < baseStr.length(); i++){\n            int root = dsu.root(baseStr.charAt(i) - 97);\n            sb.append((char)(dsu.min[root] + 97));\n\n        }\n        return sb.toString();\n    }\n    \n    class UFDS{\n        \n        int[] id;\n        int[] size;\n        int[] min;\n        \n        public UFDS(int N){\n            \n            id = new int[N];\n            size = new int[N];\n            min = new int[N];\n            for(int i = 0; i < N; i++){\n                id[i] = i;\n                size[i] = 1;\n                min[i] = i;\n            }\n        }\n        \n        private int root(int i){\n            while (i != id[i]){\n                id[i] = id[id[i]];\n                i = id[i];\n            }\n            return i;\n        }\n        \n        public void union(int p, int q){\n            \n            int i = root(p);\n            int j = root(q);\n            if(i == j)return;\n            if(size[i] < size[j]){\n                id[i] = id[j];\n                size[j] += size[i];\n                min[j] = Math.min(min[i],min[j]);\n            }\n            else{\n                id[j] = id[i];\n                size[i] += size[j];\n                min[i] = Math.min(min[i],min[j]);\n            }\n        }\n\n    }   \n}\n```
['Union Find', 'Java']