Lexicographically Smallest Equivalent String | Leetcode 1061

class Solution {
    int find(vector<int>& dsuf,int v){
        if(dsuf[v]==-1)
            return v;
        return dsuf[v]=find(dsuf,dsuf[v]);
    }
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        vector<int> dsuf(26,-1);

        //Step-1: Build Disjoint Joint equivalent sets (with smallest in each set as absolute parent)
        for(int i=0;i<s1.size();++i){
            if(s1[i]==s2[i])    continue;

            int px = find(dsuf,s1[i]-'a');
            int py = find(dsuf,s2[i]-'a');
            if(px==py)//Already in same set
                continue;
            
            //Union by smallest char as absolute parent
            if(px>py)   dsuf[px]=py;
            else        dsuf[py]=px;
        }
        //Step-2: Iterate for baseStr and find lexicographical smallest equivalent string
        string res;
        for(int i=0;i<baseStr.size();++i){
            int parent = find(dsuf,baseStr[i]-'a');
            res.push_back(char(parent+97));
        }
        return res;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    private int find(int[] dsuf, int v) {
        if (dsuf[v] == -1)
            return v;
        return dsuf[v] = find(dsuf, dsuf[v]);
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] dsuf = new int[26];
        Arrays.fill(dsuf, -1);

        // Step-1: Build Disjoint Joint equivalent sets (with smallest in each set as absolute parent)
        for (int i = 0; i < s1.length(); ++i) {
            if (s1.charAt(i) == s2.charAt(i)) continue;

            int px = find(dsuf, s1.charAt(i) - 'a');
            int py = find(dsuf, s2.charAt(i) - 'a');
            if (px == py) continue;

            // Union by smallest char as absolute parent
            if (px > py) dsuf[px] = py;
            else dsuf[py] = px;
        }

        // Step-2: Iterate for baseStr and find lexicographical smallest equivalent string
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < baseStr.length(); ++i) {
            int parent = find(dsuf, baseStr.charAt(i) - 'a');
            res.append((char) (parent + 'a'));
        }
        return res.toString();
    }
}

#Python
class Solution:
    def find(self, dsuf, v):
        if dsuf[v] == -1:
            return v
        dsuf[v] = self.find(dsuf, dsuf[v])
        return dsuf[v]

    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        dsuf = [-1] * 26

        # Step-1: Build Disjoint Joint equivalent sets (with smallest in each set as absolute parent)
        for i in range(len(s1)):
            if s1[i] == s2[i]:
                continue

            px = self.find(dsuf, ord(s1[i]) - ord('a'))
            py = self.find(dsuf, ord(s2[i]) - ord('a'))
            if px == py:
                continue

            # Union by smallest char as absolute parent
            if px > py:
                dsuf[px] = py
            else:
                dsuf[py] = px

        # Step-2: Iterate for baseStr and find lexicographical smallest equivalent string
        res = []
        for c in baseStr:
            parent = self.find(dsuf, ord(c) - ord('a'))
            res.append(chr(parent + ord('a')))
        return ''.join(res)
*/