Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Character equivalence is transitive, so the given pairs form connected groups. Each position of the base string can independently become the smallest character in its group. A disjoint-set structure can keep that smallest character as the group's representative.

Approach

Create parent entries as characters are encountered. Use path compression in find, and merge each pair from s1 and s2 by attaching the lexicographically larger root to the smaller root. This preserves the minimum representative after every union. Replace each character in baseStr with its final root and join the results. A character never appearing in an equivalence pair remains its own representative.

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        n = len(s1)
        uf = {}

        def find(x):
            if not x in uf:
                uf[x] = x
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]

        def union(x, y):
            root1 = find(x)
            root2 = find(y)
            if root1 > root2:
                uf[root1] = root2
            else:
                uf[root2] = root1

        for i in range(n):
            union(s1[i], s2[i])

        res = []
        for x in baseStr:
            res.append(find(x))

        return "".join(res)

Complexity analysis

Let n = s1.length and b = baseStr.length. Union-find operations over the fixed 26-letter alphabet are effectively constant, so time is O(n + b). Auxiliary space is O(b) for the result list built before joining, plus fixed O(26) union-find state; the returned string also has O(b) characters.