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 constructor(size) {
3 this.parent = Array.from({ length: size }, (_, index) => index);
4 }
5
6 find(x) {
7 if (this.parent[x] !== x) {
8 this.parent[x] = this.find(this.parent[x]);
9 }
10 return this.parent[x];
11 }
12
13 union(x, y) {
14 const rootX = this.find(x);
15 const rootY = this.find(y);
16 if (rootX !== rootY) {
17 this.parent[Math.max(rootX, rootY)] = Math.min(rootX, rootY);
18 }
19 }
20}
21
22function smallestEquivalentString(s1, s2, baseStr) {
23 const uf = new UnionFind(26);
24 for (let i = 0; i < s1.length; i++) {
25 uf.union(s1.charCodeAt(i) - 'a'.charCodeAt(0), s2.charCodeAt(i) - 'a'.charCodeAt(0));
26 }
27
28 const smallestChar = Array.from({ length: 26 }, (_, i) => String.fromCharCode(uf.find(i) + 'a'.charCodeAt(0)));
29 return Array.from(baseStr, c => smallestChar[c.charCodeAt(0) - 'a'.charCodeAt(0)]).join('');
30}
31
32// Example usage
33console.log(smallestEquivalentString("parker", "morris", "parser")); // Output: "makkek"This JavaScript solution employs a UnionFind class to unify characters into groups based on equivalence. The `baseStr` is then processed to transform each character to its smallest equivalent character based on the established groups.
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.