I use a Union-Find data structure to maintain equivalence classes between characters from s1 and s2. For each pair (s1[i], s2[i]), I unify their groups such that the representative (or parent) of the group is always the smallest character lexicographically. Once all equivalence relations are processed, I iterate over baseStr, and for each character, I replace it with its group's representative — which ensures that I get the lexicographically smallest equivalent string.
class Solution:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
parent = [i for i in range(26)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return
if px < py:
parent[py] = px
else:
parent[px] = py
for c1, c2 in zip(s1, s2):
union(ord(c1) - ord('a'), ord(c2) - ord('a'))
result = []
for c in baseStr:
smallest_char = chr(find(ord(c) - ord('a')) + ord('a'))
result.append(smallest_char)
return ''.join(result)- Time: O(n + m + k·α(26)) ≈ O(n + m + k), where n = len(s1), m = len(s2), k = len(baseStr), α = Inverse Ackermann function (very small).
- Space: O(1)
