1061. Lexicographically Smallest Equivalent String

Problem¶

Given character pairs from s1 and s2, treat each pair as equivalent under transitivity. Replace every character in baseStr with the smallest letter in its equivalence class.

s1="abc", s2="cde", baseStr="eed"
classes={a,c,e}, {b,d} -> output="aab"

Key trick¶

Use disjoint-set union (DSU), always making the smallest root the representative of its entire equivalence class.

Trap¶

When merging two classes, update the parent of the root, not the original character; otherwise an existing class can be disconnected.

Why is it interesting?¶

It models equivalence relations as connected components while requiring each component to maintain a canonical, lexicographically smallest representative.

Python solution¶

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        parent = list(range(26))

        def find(x):
            # Path compression makes future lookups direct.
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y) -> None:
            root_x = find(x)
            root_y = find(y)

            # The smallest letter must represent the merged class.
            if root_x < root_y:
                parent[root_y] = root_x
            elif root_y < root_x:
                parent[root_x] = root_y

        for ch1, ch2 in zip(s1, s2):
            union(ord(ch1) - ord("a"), ord(ch2) - ord("a"))

        return "".join(
            chr(find(ord(ch) - ord("a")) + ord("a"))
            for ch in baseStr
        )

Time complexity: \(O(|s1| + |baseStr|)\) because the alphabet has only 26 letters.

Auxiliary space: \(O(26)\), excluding the returned string.

Comment on my solution¶

Your DSU choice and find implementation are correct. The bug is in union: it changes the parent of ch1 or ch2 instead of the parent of their roots.

if root_1 < root_2:
    parent[root_2] = root_1
else:
    parent[root_1] = root_2

For example, if ch2 already belongs to a larger class, assigning parent[ch2] does not merge that entire class and can overwrite its existing connection.

# Wrong Answer: 106/117 testcases passed
# "leetcode", "programs", "sourcecode"
# Output: "eauccecade"
# Expected: "aauaaaaada"
class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        parent = {ch:ch for ch in "abcdefghijklmnopqrstuvwxyz"}
        def find(ch):
            if parent[ch] != ch:
                parent[ch] = find(parent[ch])
            return parent[ch]
        def union(ch1, ch2):
            root_1 = find(ch1)
            root_2 = find(ch2)
            if root_1 != root_2:
                if root_1 < root_2:
                    parent[ch2] = root_1
                else:
                    parent[ch1] = root_2
        for ch1, ch2 in zip(s1,s2):
            union(ch1, ch2)
        return "".join(map(find, baseStr))