Sponsored
Sponsored
The idea is to use a union-find data structure to record the equivalence relationships between characters. The union operation will merge sets of equivalent characters.
Next, for each character, we find its representative in the equivalence class (or set), and map each character to the lexicographically smallest character in its set, thus ensuring the smallest equivalent transformation.
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the length of baseStr.
Space Complexity: O(ALPHABET_SIZE), which is constant due to the fixed size of the alphabet.
1class UnionFind:
2 def __init__(self, size):
3 self.parent = list(range(size))
4
5 def find(self, x):
6 if self.parent[x] != x:
7 self.parent[x] = self.find(self.parent[x])
8 return self.parent[x]
9
10 def union(self, x, y):
11 rootX = self.find(x)
12 rootY = self.find(y)
13 if rootX != rootY:
14 self.parent[max(rootX, rootY)] = min(rootX, rootY)
15
16
17def smallest_equivalent_string(s1: str, s2: str, base_str: str) -> str:
18 uf = UnionFind(26)
19 for a, b in zip(s1, s2):
20 uf.union(ord(a) - ord('a'), ord(b) - ord('a'))
21
22 smallest_char = [chr(uf.find(i) + ord('a')) for i in range(26)]
23 return ''.join(smallest_char[ord(c) - ord('a')] for c in base_str)
24
25
26# Example usage
27s1 = "parker"
28s2 = "morris"
29baseStr = "parser"
30print(smallest_equivalent_string(s1, s2, baseStr)) # Output: "makkek"This Python solution includes a UnionFind class to manage groupings of equivalent characters. By processing pairs of characters from s1 and s2 with the union operation, the equivalent sets are found. Finally, each character in baseStr is transformed to its smallest equivalent using these groupings.
Another method is treating each character as a node in a graph where edges connect equivalent nodes (characters). Perform Depth-First Search (DFS) to find all characters that belong to an equivalence group.
Once we have gathered all groups and established the smallest character for each group, we can form the desired output by mapping each baseStr character to the smallest in its equivalence class.
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the number of edges in the graph (size of baseStr).
Space Complexity: O(ALPHABET_SIZE), due to the storage of graph nodes and mappings.
1def build_graph(s1, s2):
2 graph = {chr(
This Python function constructs a graph from the equivalences given in s1 and s2. It then performs DFS to determine the connected components of the graph, which represent equivalence classes. After identifying each group, it maps all characters in the group to their minimum character to construct the smallest equivalent string for baseStr.