Solution in c++ using DSU
Intuition\n The problem is asking to find the smallest equivalent string of a given string "baseStr" by making a series of replacements based on the two input s
# Intuition\n The problem is asking to find the smallest equivalent string of a given string "**baseStr**" by making a series of replacements based on the two input strings "**s1**" and "**s2**". The idea is to form a union of characters that are equivalent, and then replace the characters in "**baseStr**" with their equivalent parent.\n\n# Approach\nThe solution uses a **Disjoint-Set** data structure to keep track of the equivalent characters. For each pair of characters in "**s1**" and "**s2**" that are different, their parents in the Disjoint-Set are joined. Then, for each character in "**baseStr**", its equivalent parent in the **Disjoint-Set** is found and replaced if it is smaller than the current character.\n\n# Complexity\n- Time complexity:\nThe time complexity is ***O(n log* n)**, where ***n*** is the number of characters in the input strings. This is because the Disjoint-Set uses path compression and union by size, which results in an almost constant time complexity for the union and find operations.\n\n- Space complexity:\nThe space complexity is ***O(26)*** as it only needs to store 26 disjoint sets and it is a constant space.\n\n# Code\n```\nclass Solution {\npublic:\n// Node struct to represent a character and its properties in the Disjoint-Set\nstruct Node{\n    int id =-1; // id of the character, initialize it to -1 to represent uninitialized state\n    char label=\' \'; // label of the character, initialize it to \' \' to represent uninitialized state\n    Node* parent=this; // pointer to the parent node, initialize it to this to represent the root node\n    int size=1; // size of the set, initialize it to 1 as it is the root node\n    bool visted=0; // boolean to check if the node is visited, not used in this code\n    vector<Node*> neighbours={}; // neighbours of the node, not used in this code\n    Node(int _id, char _label):id(_id), label(_label){} // constructor to initialize the id and label of the node\n};\n\n// function to find the parent of a node in the Disjoint-Set\nNode* getParentDSU(Node* node){\n    if(node==node->parent) return node; // if the node is the root node, return it\n    return node->parent=getParentDSU(node->parent); // else recursively find the parent and use path compression to update the parent\n}\n\n// function to join two nodes in the Disjoint-Set\nvoid joinDSU(Node* src,Node* tar){\n    src=getParentDSU(src); // find the parent of the source node\n    tar=getParentDSU(tar); // find the parent of the target node\n    if(src!=tar){ // if the two parents are different\n        if(tar->label<src->label) swap(src,tar); // ensure the label of the parent is lexicographically smaller\n        tar->parent=src; // set the parent of target to source\n        src->size+=tar->size; // increment the size of the set\n    }\n}\n\nstring smallestEquivalentString(string s1, string s2, string baseStr) {\n    // Create an array of nodes representing each character\n    vector<Node*> nodes(26);\n    for(int i=0;i<26;i++){\n        nodes[i] =  new Node(i+1,\'a\'+i); // initialize the nodes with id and label\n    }\n\n    // For each pair of characters in s1 and s2, join their parents in the Disjoint-Set\n    for(int i=0;i<s1.size();i++){\n            joinDSU(nodes[s1[i]-\'a\'],nodes[s2[i]-\'a\']);\n    }\n\n    // For each character in baseStr, replace it with its equivalent parent in the Disjoint-Set\n    for(int i=0;i<baseStr.size();i++){\n        if(getParentDSU(nodes[baseStr[i]-\'a\'])->label<baseStr[i]){\n            baseStr[i]=getParentDSU(nodes[baseStr[i]-\'a\'])->label;\n        }\n   \n}\n\n    return baseStr;\n}\n};\n```
['Graph', 'C++']