Hello, curious coders! š§āš» Today, we're diving into a fun string manipulation and graph problem from LeetCode ā Lexicographically Smallest Equivalent String. We'll break it down step-by-step and walk through a clean and efficient solution using Disjoint Set Union (Union-Find). Let's get started! š
š Problem Statement
You're given two strings s1 and s2 of the same length. Each index in these strings represents an equivalency relationship ā for example, if s1[i] == 'a' and s2[i] == 'b', then 'a' and 'b' are equivalent. These equivalencies follow the rules of an equivalence relation:
Reflexive: 'a' == 'a'
Symmetric: If 'a' == 'b', then 'b' == 'a'
Transitive: If 'a' == 'b' and 'b' == 'c', then 'a' == 'c'
You're also given a third string, baseStr. Your task is to transform every character in baseStr to the lexicographically smallest equivalent character possible using the relationships defined in s1 and s2.
š§ Intuition and Approach
We treat each letter as a node in a graph, and each pair (s1[i], s2[i]) as an edge connecting two nodes. The idea is to group all connected characters and replace each one in baseStr with the smallest character in its group.
This is where Disjoint Set Union (DSU) comes to the rescue! š”
āļø Key DSU Operations
Find: Determine the root representative of a character.
Union: Connect two characters, always attaching the one with the lexicographically smaller character as the parent.
šØāš» C++ Implementation with unionByLex()
class Solution {
public:
class DSU {
vector<int> parent;
public:
DSU(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) parent[i] = i;
}
int findPar(int u) {
if (parent[u] != u) parent[u] = findPar(parent[u]);
return parent[u];
}
void unionByLex(int u, int v) {
int pu = findPar(u);
int pv = findPar(v);
if (pu == pv) return;
if (pu < pv) parent[pv] = pu;
else parent[pu] = pv;
}
};
string smallestEquivalentString(string s1, string s2, string baseStr) {
DSU dsu(26);
for (int i = 0; i < s1.size(); ++i) {
dsu.unionByLex(s1[i] - 'a', s2[i] - 'a');
}
for (int i = 0; i < baseStr.size(); ++i) {
baseStr[i] = dsu.findPar(baseStr[i] - 'a') + 'a';
}
return baseStr;
}
};
š JavaScript Version
var smallestEquivalentString = function(s1, s2, baseStr) {
const parent = new Array(26).fill(0).map((_, i) => i);
const find = (x) => {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
const union = (x, y) => {
let px = find(x);
let py = find(y);
if (px === py) return;
if (px < py) parent[py] = px;
else parent[px] = py;
}
for (let i = 0; i < s1.length; i++) {
union(s1.charCodeAt(i) - 97, s2.charCodeAt(i) - 97);
}
let result = "";
for (let ch of baseStr) {
result += String.fromCharCode(find(ch.charCodeAt(0) - 97) + 97);
}
return result;
};
š Python Version
def smallestEquivalentString(s1: str, s2: str, baseStr: str) -> str:
parent = [i for i in range(26)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px = find(x)
py = find(y)
if px == py:
return
if px < py:
parent[py] = px
else:
parent[px] = py
for a, b in zip(s1, s2):
union(ord(a) - ord('a'), ord(b) - ord('a'))
result = ''
for ch in baseStr:
result += chr(find(ord(ch) - ord('a')) + ord('a'))
return result
š Test Cases
Let's validate our solution with a few diverse cases:
Input:
s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Input:
s1 = "hello", s2 = "world", baseStr = "hold"
Output: "hdld"
Input:
s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
Output: "aauaaaaada"
// Unique test case:
Input:
s1 = "abc", s2 = "xyz", baseStr = "cba"
Output: "xyz" // Because 'a' -> 'x', 'b' -> 'y', 'c' -> 'z'
Input:
s1 = "abcabc", s2 = "defdef", baseStr = "fed"
Output: "aaa" // All letters map to the smallest in their equivalence class
š Time and Space Complexity
Time Complexity: O(n + m) // n = s1.size(), m = baseStr.size()
Space Complexity: O(1) // Only 26 lowercase letters stored
āØ Wrap Up
This problem is a perfect combo of strings and graphs and gives you a solid practice on Union-Find ā a super important concept in computer science. Learning it here with such a fun problem is a win-win! šÆ
If you found this helpful, feel free to ā¤ļø and follow for more beginner-friendly walkthroughs!
Happy coding! šØāš»āØ
