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.
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class UnionFind {
8public:
9 vector<int> parent;
10
11 UnionFind(int size) {
12 parent.resize(size);
13 for (int i = 0; i < size; ++i)
14 parent[i] = i;
15 }
16
17 int find(int x) {
18 if (parent[x] != x)
19 parent[x] = find(parent[x]);
20 return parent[x];
21 }
22
23 void unionSets(int x, int y) {
24 int rootX = find(x);
25 int rootY = find(y);
26 if (rootX != rootY)
27 parent[rootY] = rootX;
28 }
29};
30
31string smallestEquivalentString(string s1, string s2, string baseStr) {
32 UnionFind uf(26);
33 for (int i = 0; i < s1.size(); ++i) {
34 uf.unionSets(s1[i] - 'a', s2[i] - 'a');
35 }
36 vector<char> smallestChar(26);
37 for (int i = 0; i < 26; ++i)
38 smallestChar[i] = i + 'a';
39 for (int i = 0; i < 26; ++i) {
40 int root = uf.find(i);
41 smallestChar[root] = min(smallestChar[root], (char)(i + 'a'));
42 }
43 string result;
44 result.reserve(baseStr.size());
45 for (char c : baseStr) {
46 char rootChar = smallestChar[uf.find(c - 'a')];
47 result.push_back(rootChar);
48 }
49 return result;
50}
51
52int main() {
53 string s1 = "parker";
54 string s2 = "morris";
55 string baseStr = "parser";
56 cout << smallestEquivalentString(s1, s2, baseStr) << endl; // Output: "makkek"
57 return 0;
58}The solution makes use of a custom UnionFind class to manage equivalence relations between the characters. Once the unions are performed for all character pairs, each character is replaced with its lexicographically smallest equivalent using a lookup table prepared with the smallest character for each set.
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.