🔥Python3🔥 Union-find (Template + Explanations)
Intuition\n - The rules for the "equivalent characters" introduced in the problem simply means the two characters belong to the same group.\n - And our job is t
**Intuition**\n - The rules for the "equivalent characters" introduced in the problem simply means **the two characters belong to the same group**.\n - And our job is that for each character in ```baseStr```, we need to find its belonging group and find the smallest character from that group.\n - So we have two tasks:\n \t- Create all the groups with equivalent characters from ```s1``` and ```s2```.\n \t- Find the group for each character in ```baseStr```, and find the smallest character in that group\n\n Grouping connected elements can be done using DFS/BFS/Union-find, I personally like Union-find because it makes the most sense, and very easy to implement using a template. If you don\'t know about union-find or don\'t have a good template, I put the best one I know below which I used a lot.\n\n**Basic Union-find template**\n\n```python\n# UF is a hash map where you can find the root of a group of elements giving an element.\n# A key in UF is a element, UF[x] is x\'s parent.\n# If UF[x] == x meaning x is the root of its group.\nUF = {}\n\n# Given an element, find the root of the group to which this element belongs.\ndef find(x):\n    # this may be the first time we see x, so set itself as the root.\n    if x not in UF:\n        UF[x] = x\n    # If x == UF[x], meaning x is the root of this group.\n    # If x != UF[x], we use the find function again on x\'s parent UF[x] \n    # until we find the root and set it as the parent (value) of x in UF.\n    if x != UF[x]:\n        UF[x] = find(UF[x])\n    return UF[x]\n\n# Given two elements x and y, we know that x and y should be in the same group, \n# this means the group that contains x and the group that contains y \n# should be merged together if they are currently separate groups.\n# So we first find the root of x and the root of y using the find function.\n# We then set the root of y (rootY) as the root of the root of x (rootX).\ndef union(x, y):\n\n    rootX = find(x)\n    rootY = find(y)\n    # set the root of y (rootY) as the root of the root of x (rootX)\n    UF[rootX] = rootY\n```\n\nThe tricky part in this problem using Union-find template is to set the smallest element in a group as root of that group. Please see the changes below. \n\n**Union-find Solution**\n```python\nclass Solution:\n    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n        \n        UF = {}\n        def find(x):\n            UF.setdefault(x,x)\n            if x != UF[x]:\n                UF[x] = find(UF[x])\n            return UF[x]\n        \n        def union(x,y):\n            rootX = find(x)\n            rootY = find(y)\n            # The main issue we need to take care of in this problem is\n            # that we want the root of a group to be \n            # the smallest element in the group\n            # So every time we add an element in a group, we check if it is the smallest one,\n            # If it is, we set it as the root.\n            if rootX>rootY:\n                UF[rootX] = rootY\n            else:\n                UF[rootY] = rootX\n        \n        # Union the two equivalent characters\n        # at the same position from s1 and s2 into the same group.\n        for i in range(len(s1)):\n            union(s1[i],s2[i])\n        \n        # Simply find the root of the group a character belongs to\n        # Note that if c is not in any group, \n        # we have UF.setdefault(x,x) in def find(x) to take care of it\n        res = []\n        for c in baseStr:\n            res.append(find(c))\n            \n        return \'\'.join(res)\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]