1061. Lexicographically Smallest Equivalent String

Intuition

Union Find.

Approach

The trick here is to make the ‘smaller’ character the new ‘parent’ during the union() operation, instead of basing it on the size of connected components (rank).

Complexity

Time complexity

Assuming the number of unique characters is $S$, the union() operation will have a runtime of $O(\log S)$. If the length of s1 (or s2) is $N$, and the length of baseStr is $M$, it involves performing union() $N$ times and find() $M$ times. Therefore, the overall time complexity is $O((N+M)\log S)$. Given that $S$ is 26 in this case, it simplifies to $O(M+N)$.

Space complexity

$O(S)$, i.e, $O(1)$ to maintain the parent dict.

Code

class UnionFind:
    def __init__(self):
        self.parent = dict()
        for c in "abcdefghijklmnopqrstuvwxyz":
            self.parent[c] = c
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        r1 = self.find(x)
        r2 = self.find(y)
        # trick
        if r1 > r2:
            r1, r2 = r2, r1
        self.parent[r2] = r1

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        uf = UnionFind()
        for c1, c2 in zip(s1, s2):
            uf.union(c1, c2)
        
        res = []
        for c in baseStr:
            res.append(uf.find(c))
        return ''.join(res)