✅✅ C++ || Union Find || Beat 100 % || DSU ✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DSU {\npublic:\n    vector<int>rank;\n    vector<int>parent;\n    \n    DSU(int n) {\n        rank.resize(n);\n        parent.resize(n);\n        for (int i = 0; i < n; i++) {\n            rank[i] = i;\n            parent[i] = i;\n        }\n    }\n    \n    int findParent(int x) {\n        if (x == parent[x]) {\n            return x;\n        }\n        return parent[x] = findParent(parent[x]);\n    }\n    \n    void makeUnion(int x, int y) {\n        int p1 = findParent(x), p2 = findParent(y);\n        if (p1 != p2) {\n            if (rank[p1] < rank[p2]) {\n                parent[p2] = p1;\n            }\n            else {\n                parent[p1] = p2;\n            }\n        }\n    }\n};\n\nclass Solution {\npublic:\n    string smallestEquivalentString(string s1, string s2, string baseStr) {\n        DSU dsu(26);\n        for (int i = 0; i < s1.size(); i++) {\n            dsu.makeUnion(s1[i]-\'a\', s2[i]-\'a\');\n        }\n        string ans;\n        for (int i = 0; i < baseStr.size(); i++) {\n            char ch = dsu.findParent(baseStr[i]-\'a\') + \'a\';\n            ans += ch;\n        }\n        return ans;\n    }\n};\n```\n\n![upvote1.jpeg](https://assets.leetcode.com/users/images/fd306d17-746c-4363-94cd-6f52a7fa0888_1673677839.7584035.jpeg)\n
['C++']