Lexicographically Smallest Equivalent String
Problem
You are given two strings s1 and s2 of the same length, where s1[i] and s2[i] are declared equivalent. Equivalence is reflexive, symmetric, and transitive. Given a third string baseStr, return the lexicographically smallest string obtainable by replacing each character of baseStr with an equivalent character.
s1 = "parker", s2 = "morris", baseStr = "parser""makkek"def smallest_equivalent_string(s1, s2, base_str):
parent = list(range(26))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return
hi, lo = max(ra, rb), min(ra, rb)
parent[hi] = lo # smaller letter becomes the root
for a, b in zip(s1, s2):
union(ord(a) - 97, ord(b) - 97)
return "".join(chr(find(ord(c) - 97) + 97) for c in base_str)function smallestEquivalentString(s1, s2, baseStr) {
const parent = Array.from({ length: 26 }, (_, i) => i);
function find(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
function union(a, b) {
const ra = find(a), rb = find(b);
if (ra === rb) return;
const hi = Math.max(ra, rb), lo = Math.min(ra, rb);
parent[hi] = lo; // smaller letter becomes the root
}
for (let i = 0; i < s1.length; i++) {
union(s1.charCodeAt(i) - 97, s2.charCodeAt(i) - 97);
}
let out = "";
for (const c of baseStr) out += String.fromCharCode(find(c.charCodeAt(0) - 97) + 97);
return out;
}class Solution {
int[] parent = new int[26];
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
int hi = Math.max(ra, rb), lo = Math.min(ra, rb);
parent[hi] = lo; // smaller letter becomes the root
}
public String smallestEquivalentString(String s1, String s2, String baseStr) {
for (int i = 0; i < 26; i++) parent[i] = i;
for (int i = 0; i < s1.length(); i++)
union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
StringBuilder sb = new StringBuilder();
for (char c : baseStr.toCharArray())
sb.append((char) (find(c - 'a') + 'a'));
return sb.toString();
}
}class Solution {
int parent[26];
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void uni(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
int hi = max(ra, rb), lo = min(ra, rb);
parent[hi] = lo; // smaller letter becomes the root
}
public:
string smallestEquivalentString(string s1, string s2, string baseStr) {
for (int i = 0; i < 26; i++) parent[i] = i;
for (int i = 0; i < (int)s1.size(); i++)
uni(s1[i] - 'a', s2[i] - 'a');
string out;
for (char c : baseStr) out += (char)(find(c - 'a') + 'a');
return out;
}
};Explanation
The key insight is that equivalence spreads: if a equals b and b equals c, then all three are interchangeable. So we want to gather letters into groups, and for each group pick the smallest letter to represent everyone in it.
This is exactly what Union-Find does. We keep a parent array for the 26 letters where each letter starts as its own group. The clever twist in union is that when two groups merge, the smaller letter always becomes the root (parent[hi] = lo). That guarantees every group's root is its alphabetically smallest member.
We process each pair s1[i] and s2[i] by calling union on them. After all pairs are merged, we rebuild baseStr by replacing each character with the root of its group via find.
Example: with s1 = "parker" and s2 = "morris" we get groups {m,p}, {a,o}, {k,r,s}, {e,i}. The character p maps to m, a stays a (smallest), and r,s map to k.
So "parser" becomes "makkek". Because each letter just looks up its group's smallest root, we always get the lexicographically smallest result.