Smallest Equivalent String
Problem
Two strings a and b of equal length declare letter equivalences: a[i] is equivalent to b[i] for every i. Equivalence is reflexive, symmetric and transitive, so it groups the lowercase letters into classes. Given a third string text, replace each of its letters with the smallest letter of its class and return the alphabetically smallest string this produces.
Examples
Input: a = "parker", b = "morris", text = "parser"
Output: "makkek"
Why: the classes include {m, p}, {a, o}, {k, r, s} and {e, i}Input: a = "hello", b = "world", text = "hold"
Output: "hdld"
Why: o shares a class with e and d, so it becomes d; h, l and d already lead theirsInput: a = "", b = "", text = "abc"
Output: "abc"
Why: edge case, with no equivalences every letter stands aloneHints
0 / 3
The pairs chain together: if a is equivalent to c and c to e, then a is equivalent to e even though no pair says so directly. You need whole classes, not single pairs.
A disjoint-set structure over the 26 letters builds the classes as the pairs are read. The only question left is which letter each class should report.
When two classes merge, always make the smaller letter the root. Then the root of any letter is the smallest letter in its class, and the answer maps every letter of text to its root.
Solution
Every pair merges two classes of letters, and transitivity is exactly what a disjoint-set structure provides for free. The twist is choosing the representative: if every merge hangs the root with the larger letter under the root with the smaller letter, each root is always the smallest letter of its class. Replacing each letter of text by its root therefore gives the smallest letter at every position independently, which is the smallest possible string overall. Path halving keeps the finds short. With an alphabet of 26 letters, time is O(n plus m) for the pair and text lengths, and space is O(1).
def smallest_equivalent(a, b, text):
parent = {}
def find(x):
parent.setdefault(x, x)
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for x, y in zip(a, b):
rx, ry = sorted((find(x), find(y)))
parent[ry] = rx # the smaller letter stays root
return "".join(find(ch) for ch in text)
print(smallest_equivalent("parker", "morris", "parser")) # -> makkek
print(smallest_equivalent("hello", "world", "hold")) # -> hdld
print(smallest_equivalent("", "", "abc")) # -> abc
print(smallest_equivalent("leetcode", "programs", "sourcecode")) # -> aauaaaaadaStuck on the idea rather than the code? Path Compression covers it.