[C++/Java/Python] | DSU/UF Approach O(NLogN) ✅
USING THE BASIC TEMPLATE OF DSU (DISJOINT SET)\n\nIntuition:\nThe intuition behind using a disjoint set (DSU) in this problem is to create an equivalence relati
**`USING THE BASIC TEMPLATE OF DSU (DISJOINT SET)`**\n\n**Intuition**:\nThe intuition behind using a `disjoint` set (DSU) in this problem is to create an `equivalence` relationship between the characters in the `two` input strings `s1` and `s2`. The goal is to find the smallest equivalent string using the base string `baseStr`, so the idea is to group the characters in `s1` and `s2` that are `equivalent` and `replace` them with the `smallest` character in that group.\n\n**Approach**:\n\n1. Initialize a disjoint set of size `26`, representing the 26 characters in the alphabet.\n2. Iterate through the characters of the **two** input strings **s1** and **s2**, and for each pair of characters `(s1[i], s2[i])`, use the `unionBySize` function of the disjoint set to create an equivalence relationship between them by merging the sets they belong to. This step ensures that all characters that are equivalent in `s1` and `s2` are in the same set.\n3. Iterate through the characters in the base string **baseStr** and for each character, use the **findPar** function of the `disjoint` set to find the representative character of the set that the character belongs to.\n4. Append the representative character to the `result` string, this will be the `smallest` equivalent character for the current character in the base string `baseStr`.\n5. Return the result `string`\n\nBy the end of the above steps, the `result` string will be the smallest equivalent string. The approach is using` DSU `for creating an equivalent relationship between the characters in `s1` and `s2`, and then using `findPar` to find the `smallest` character in the set for each character in the base string `baseStr`.\n\n----\n\n**Codes:**\n\n**C++:**\n```\nclass DisjointSet{\n    vector<int>parent,size;\n public:\n    DisjointSet(int n) {\n        parent.resize(n+1);\n        size.resize(n+1); \n        for(int i = 0;i<=n;i++) {\n            parent[i] = i; \n            size[i] = 1; \n        }\n\t}\n    int findPar(int node){\n        if(node==parent[node]) return node;\n        return parent[node] =findPar(parent[node]);\n    }\n    void unionBySize(int u, int v) {\n        int up = findPar(u); \n        int uv = findPar(v); \n        if(up == uv) return; \n        if(up < uv) {\n            parent[uv] = up; \n        }\n        else {\n            parent[up] = uv;\n        }\n    }\n};\nclass Solution {\npublic:\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        int n = s1.size();\n        DisjointSet ds(26);\n        for(int i=0;i<n;i++){\n            ds.unionBySize(s1[i]-\'a\',s2[i]-\'a\');\n        }\n        string res="";\n        for(int i=0;i<baseStr.size();i++){\n            res+=(char)(ds.findPar(baseStr[i]-\'a\')+\'a\');\n        }\n        return res;\n    }\n};\n```\n\n----\n**Java:**\n```\nclass DisjointSet{\n    int[] parent, size;\n    public DisjointSet(int n) {\n        parent = new int[n+1];\n        size = new int[n+1]; \n        for(int i = 0;i<=n;i++) {\n            parent[i] = i; \n            size[i] = 1; \n        }\n    }\n    int findPar(int node){\n        if(node==parent[node]) return node;\n        return parent[node] =findPar(parent[node]);\n    }\n    void unionBySize(int u, int v) {\n        int up = findPar(u); \n        int uv = findPar(v); \n        if(up == uv) return; \n        if(up < uv) {\n            parent[uv] = up; \n        }\n        else {\n            parent[up] = uv;\n        }\n    }\n}\nclass Solution {\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        int n = s1.length();\n        DisjointSet ds = new DisjointSet(26);\n        for(int i=0;i<n;i++){\n            ds.unionBySize(s1.charAt(i)-\'a\',s2.charAt(i)-\'a\');\n        }\n        StringBuilder res = new StringBuilder();\n        for(int i=0;i<baseStr.length();i++){\n            res.append((char)(ds.findPar(baseStr.charAt(i)-\'a\')+\'a\'));\n        }\n        return res.toString();\n    }\n}\n```\n\n----\n**Python:**\n```\nclass DisjointSet:\n    def __init__(self, n):\n        self.parent = [i for i in range(n+1)]\n        self.size = [1 for _ in range(n+1)]\n\n    def findPar(self, node):\n        if node == self.parent[node]:\n            return node\n        self.parent[node] = self.findPar(self.parent[node])\n        return self.parent[node]\n\n    def unionBySize(self, u, v):\n        up = self.findPar(u)\n        uv = self.findPar(v)\n        if up == uv:\n            return\n        if up < uv:\n            self.parent[uv] = up\n        else:\n            self.parent[up] = uv\n\nclass Solution:\n    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n        n = len(s1)\n        ds = DisjointSet(26)\n        for i in range(n):\n            ds.unionBySize(ord(s1[i]) - ord(\'a\'), ord(s2[i]) - ord(\'a\'))\n        res = ""\n        for i in range(len(baseStr)):\n            res += chr(ds.findPar(ord(baseStr[i]) - ord(\'a\')) + ord(\'a\'))\n        return res\n```\n\n\n----\nThe **Time Complexity** of this approach is **O(n log n)**, where `n` is the number of characters in baseStr, due to the use of union-by-size and the `findPar` function. \nThe **Space Complexity** is **O(n)**, where `n` is the number of characters in the alphabet used in the input strings, due to the use of a disjoint set with one representative per set.
['Union Find', 'C', 'Python', 'Java']