Saved from https://leetcode.com/problems/lexicographically-smallest-equivalent-string/

lc1061

class Solution {
    // Typical union find problem
    // Time: O(n *26), where n is len(A)
    // Space: O(26)
    public String smallestEquivalentString(String A, String B, String S) {
        UnionFind uf = new UnionFind();
        for (int i = 0; i < A.length(); i++) {
            uf.union(A.charAt(i), B.charAt(i));
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < S.length(); i++) {
            res.append(uf.find(S.charAt(i)));
        }
        return res.toString();
    }

    // A variant of union find algorithm (quick-union) where we the smaller id/letter as the root (as requested by the question)
    public static class UnionFind {
        int[] ids;
        public UnionFind() {
            ids = new int[26];
            for (int i = 0; i< 26; i++) {
                ids[i] = i;
            }
        }
        
        // Time: O(26)
        public char find(char i) {
            int id = i - 'a';
            while (ids[id] != id) {
                id = ids[id];
            }
            return (char)('a' + id);
        }
        
        // Time: O(26)
        public void union(char p, char q) {
            int pid = find(p) - 'a';
            int qid = find(q) - 'a';
            if (pid == qid) {
                return;
            }
            // Always use the smaller id as the root (as requested by the question)
            if (pid <= qid) {
                ids[qid] = pid;
            } else {
                ids[pid] = qid;
            }
        }
    }
}