LEARNING JOURNAL

function smallestEquivalentString(s1: string, s2: string, baseStr: string): string {
    
    // alphabet Array
    const aCharCode = "a".charCodeAt(0);
    const alphabetArr: string[] = Array.from({length: 26}).map((_, i) => String.fromCharCode(aCharCode + i)); 
    
    // An object that has UnionFind algorithm implemented under the hood
    const uF = new UnionFind(alphabetArr.length);



    // Iterate the string s1 and s2
    for(let i = 0; i < s1.length; i++) {
        // For each pair, union them (or their groups) into 1 group
        const index1 = s1.charCodeAt(i) - aCharCode;
        const index2 = s2.charCodeAt(i) - aCharCode;

        uF.union(index1, index2);
    }

    const indexArr: number[] = [];
    // Iterate the baseStr
    for(let i = 0; i < baseStr.length; i++) {
        const root = uF.findRoot(baseStr.charCodeAt(i) - aCharCode);
        indexArr.push(root);
    }

    return indexArr.map(index => alphabetArr[index]).join("");
};


class UnionFind {
    private roots:number[];

    constructor(n:number) {
        this.roots = Array.from({length:n}).map((_,i) => i);
    }

    public union(index1: number, index2:number):void {
        // union index1 and index2 (or their groups) into 1 group
        const root1 = this.findRoot(index1);
        const root2 = this.findRoot(index2);

        if(root1 === root2) return;

        if(root1 < root2) {
            this.roots[root2] = root1;
        }
        else {
            this.roots[root1] = root2;
        }
    }   

    public findRoot(charIndex:number):number {
        // find the root of charIndex
        if(charIndex === this.roots[charIndex]) {
            return charIndex;
        }

        this.roots[charIndex] = this.findRoot(this.roots[charIndex]);

        return this.roots[charIndex];
    }
}