Simple Union-find Solution [Easy to Understand]
Key Observations:\nEquivalence Relation:\nThe equivalence information given in s1 and s2 is transitive, symmetric, and reflexive. This means if \'a\' == \'b\' a
# Key Observations:\n**Equivalence Relation:**\nThe equivalence information given in s1 and s2 is transitive, symmetric, and reflexive. This means if \'a\' == \'b\' and \'b\' == \'c\', then \'a\' == \'c\'. Can be done using **grouping(union)**of alphabets.\n\n**Union-Find Data Structure:**\n**To handle the equivalence classes**, we can use a Union-Find (Disjoint Set) data structure. Each character will be part of a group where all characters in the group are equivalent.\nThe union operation will group two characters together, and the find operation will help us find the representative or "leader" of the group.\n\n**Lexicographical Order:**\nTo ensure that the final string is the smallest lexicographically, when merging two groups, **the representative** (or leader) of the group should be the **smallest character** in that group.\n\n# Approach\n1. **Initialization:**\nCreate a parent array where each character is its own parent initially, representing that each character is its own group.\n\n2. **Union Operation:**\nIterate through the strings s1 and s2 and perform the union operation on corresponding characters. This groups the equivalent characters together. And **parents the lexographically smaller** character.\n\n3. **Path Compression:**\nTo speed up the find operation, apply path compression, where every node points directly to the root representative of its group.\n\n4. **Transforming baseStr:**\nFor each character in baseStr, replace it with the representative of its equivalence group. This ensures that the smallest possible character from the group is used.\n\n5. **Result Construction:**\nBuild and return the transformed string.\n\n# Complexity\n- **Time complexity:** **O(n+m)**\nwhere n is the length of s1 or s2, m is the length of baseStr\n\n- **Space complexity:** **O(1)**\nbecause the parent array has a fixed size of 26 elements (constant space).\n\n\n# Code\n\n```JAVA []\nclass Solution {\n    private int[] parent;\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        parent = new int[26];\n        StringBuilder sb = new StringBuilder();\n        for(int i=0; i<26; i++){\n            parent[i]=i;\n        }\n        for(int i=0; i<s1.length(); i++){\n            union(s1.charAt(i)-\'a\', s2.charAt(i)-\'a\');\n        }\n        for(int i=0; i<26; i++){\n            find(i);\n        }\n        for(int i=0; i<baseStr.length(); i++){\n            sb.append(Character.toString(parent[baseStr.charAt(i)-\'a\']+\'a\'));\n        }\n        return sb.toString();\n    }\n    private int find(int a){\n        if(parent[a]!=a){\n            parent[a]=find(parent[a]);\n        }\n        return parent[a];\n    }\n    private void union(int a, int b){\n        int aRep=find(a);\n        int bRep=find(b);\n        parent[Math.max(aRep, bRep)]=Math.min(aRep, bRep);\n    }\n}\n```\n```python []\nclass Solution:\n    def __init__(self):\n        self.parent = list(range(26))\n\n    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n        self.parent = list(range(26))\n        \n        for i in range(len(s1)):\n            self.union(ord(s1[i]) - ord(\'a\'), ord(s2[i]) - ord(\'a\'))\n        \n        for i in range(26):\n            self.find(i)\n        \n        result = []\n        for char in baseStr:\n            result.append(chr(self.parent[ord(char) - ord(\'a\')] + ord(\'a\')))\n        \n        return \'\'.join(result)\n\n    def find(self, a: int) -> int:\n        if self.parent[a] != a:\n            self.parent[a] = self.find(self.parent[a])\n        return self.parent[a]\n\n    def union(self, a: int, b: int):\n        a_rep = self.find(a)\n        b_rep = self.find(b)\n        self.parent[max(a_rep, b_rep)] = min(a_rep, b_rep)\n\n```
['Union Find', 'Python', 'Java']