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 <stdio.h>
2#include <string.h>
3
4#define ALPHABET_SIZE 26
5
6int find(int parent[], int x) {
7 if (parent[x] != x) {
8 parent[x] = find(parent, parent[x]);
9 }
10 return parent[x];
11}
12
13void union_sets(int parent[], int rank[], int a, int b) {
14 int rootA = find(parent, a);
15 int rootB = find(parent, b);
16 if (rootA != rootB) {
17 if (rank[rootA] < rank[rootB])
18 parent[rootA] = rootB;
19 else if (rank[rootA] > rank[rootB])
20 parent[rootB] = rootA;
21 else {
22 parent[rootB] = rootA;
23 rank[rootA]++;
24 }
25 }
26}
27
28void smallestEquivalentString(const char* s1, const char* s2, const char* baseStr, char* result) {
29 int parent[ALPHABET_SIZE];
30 int rank[ALPHABET_SIZE] = {0};
31 for (int i = 0; i < ALPHABET_SIZE; i++) {
32 parent[i] = i;
33 }
34 int len = strlen(s1);
35 for (int i = 0; i < len; i++) {
36 union_sets(parent, rank, s1[i] - 'a', s2[i] - 'a');
37 }
38 for (int i = 0; i < ALPHABET_SIZE; i++) {
39 parent[i] = find(parent, i);
40 }
41 int baseLen = strlen(baseStr);
42 for (int i = 0; i < baseLen; i++) {
43 result[i] = parent[baseStr[i] - 'a'] + 'a';
44 }
45 result[baseLen] = '\0';
46}
47
48int main() {
49 const char *s1 = "parker";
50 const char *s2 = "morris";
51 const char *baseStr = "parser";
52 char result[100];
53 smallestEquivalentString(s1, s2, baseStr, result);
54 printf("%s\n", result); // Output: "makkek"
55 return 0;
56}This implementation initializes a union-find structure to keep track of the parent of each character (where each unique character starts as its own parent). By performing union operations on pairs of characters from s1 and s2, we merge equivalent sets.
In the final step, we find the parent of each character in baseStr and construct the smallest equivalent string.
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.