Lexicographically Smallest Equivalent String solution and explanation
Google
9 more videos on this problem
Lexicographically Smallest Equivalent String | Leetcode 1061Techdose · 16:14 · 4K views
Leetcode 1061 Lexicographically Smallest Equivalent String| Union Find Template| CodingDecoded sheetCoding Decoded · 11:41 · 2K views
Leetcode 1061. Lexicographically Smallest Equivalent String - Disjoint Set / Union-FindCode-Yao · 14:01 · 2K views
LeetCode 1061. Lexicographically Smallest Equivalent String - Interview Prep Ep 130Fisher Coder · 19:20 · 1K views
Daily Leetcode #1019: Jan 14, 2023 - 1061. Lexicographically Smallest Equivalent StringProgramming Live with Larry · 20:47 · 1K views
1061. Lexicographically Smallest Equivalent String | LeetCode | C++Deep Tech · 13:09 · 1K views
Lexicographically Smallest Equivalent String - Union Find - Graph - PythonCheatCode Ninja · 7:29 · 808 views
Leetcode 1061 Lexicographically Smallest Equivalent String (Java)TheAnalyticGuy · 10:48 · 397 views
LeetCode 1061 (Python3 Solution). Lexicographically Smallest Equivalent StringKTB World · 9:57 · 330 views
Lexicographically Smallest Equivalent String | LeetCode 1061 | JavaThe TryIt Project · 26:11 · 257 views
The problem
You are given two strings of the same length s1 and s2 and a string baseStr.
We say s1[i] and s2[i] are equivalent characters.
- For example, if
s1 = "abc"ands2 = "cde", then we have'a' == 'c','b' == 'd', and'c' == 'e'.
Equivalent characters follow the usual rules of any equivalence relation:
- Reflexivity:
'a' == 'a'. - Symmetry:
'a' == 'b'implies'b' == 'a'. - Transitivity:
'a' == 'b'and'b' == 'c'implies'a' == 'c'.
For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.
Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.
Example 1:
Input: s1 = "parker", s2 = "morris", baseStr = "parser" Output: "makkek" Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is "makkek".
Example 2:
Input: s1 = "hello", s2 = "world", baseStr = "hold" Output: "hdld" Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".
Example 3:
Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode" Output: "aauaaaaada" Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".
Constraints:
1 <= s1.length, s2.length, baseStr <= 1000s1.length == s2.lengths1,s2, andbaseStrconsist of lowercase English letters.
Approach overview
Problem Overview: You receive two strings s1 and s2 that define equivalence relationships between characters, plus a baseStr. If s1[i] equals s2[i], those characters belong to the same equivalence group. Replace each character in baseStr with the smallest lexicographical character from its equivalence group.
Approach 1: Union-Find (Disjoint Set) (Time: O((n + m) * α(26)), Space: O(26))
This approach models each lowercase letter as a node in a Union Find structure. For every pair (s1[i], s2[i]), perform a union operation to merge their sets. The key detail: always attach the larger character root to the smaller one so the representative of each set is the lexicographically smallest character. After building the structure, iterate through baseStr, find the root for each character using find(), and append that root to the result. Since the alphabet size is fixed (26), union and find operations are extremely fast with path compression.
This method is both simple and optimal. The disjoint-set structure automatically groups equivalent characters and guarantees that the representative element is the smallest possible character.
Approach 2: DFS Graph Traversal (Time: O(26 + m + n), Space: O(26 + m))
You can also treat the problem as a graph. Each character is a node, and each pair (s1[i], s2[i]) forms an undirected edge. Build an adjacency list connecting equivalent characters. Then run DFS to discover connected components. For each component, compute the smallest character and assign it as the representative for every node in that component.
After preprocessing, iterate through baseStr and replace each character with the smallest mapped value from its component. DFS works well because the graph is tiny (only 26 nodes), making traversal very cheap. The extra adjacency list storage slightly increases memory usage compared to Union-Find.
Recommended for interviews: The Union-Find approach is what interviewers usually expect. It directly models equivalence relationships and demonstrates familiarity with disjoint set structures. The DFS graph approach still shows strong understanding of connected components in a string transformation problem, but Union-Find is cleaner and easier to implement under interview pressure.
Approach 1: Union-Find Approach
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.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[max(rootX, rootY)] = min(rootX, rootY)
def smallest_equivalent_string(s1: str, s2: str, base_str: str) -> str:
uf = UnionFind(26)
for a, b in zip(s1, s2):
uf.union(ord(a) - ord('a'), ord(b) - ord('a'))
smallest_char = [chr(uf.find(i) + ord('a')) for i in range(26)]
return ''.join(smallest_char[ord(c) - ord('a')] for c in base_str)
# Example usage
s1 = "parker"
s2 = "morris"
baseStr = "parser"
print(smallest_equivalent_string(s1, s2, baseStr)) # Output: "makkek"import java.util.*;
class Solution {
public String smallestEquivalentString(String s1, String s2, String baseStr) {
int[] parent = new int[26];
for (int i = 0; i < 26; i++)
parent[i] = i;
for (int i = 0; i < s1.length(); i++) {
int a = s1.charAt(i) - 'a';
int b = s2.charAt(i) - 'a';
union(parent, a, b);
}
for (int i = 0; i < 26; i++)
parent[i] = find(parent, i);
StringBuilder result = new StringBuilder();
for (char c : baseStr.toCharArray())
result.append((char)(parent[c - 'a'] + 'a'));
return result.toString();
}
private int find(int[] parent, int x) {
if (parent[x] != x)
parent[x] = find(parent, parent[x]);
return parent[x];
}
private void union(int[] parent, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY)
parent[Math.max(rootX, rootY)] = Math.min(rootX, rootY);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.smallestEquivalentString("parker", "morris", "parser")); // Output: "makkek"
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
class UnionFind {
public:
vector<int> parent;
UnionFind(int size) {
parent.resize(size);
for (int i = 0; i < size; ++i)
parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY)
parent[rootY] = rootX;
}
};
string smallestEquivalentString(string s1, string s2, string baseStr) {
UnionFind uf(26);
for (int i = 0; i < s1.size(); ++i) {
uf.unionSets(s1[i] - 'a', s2[i] - 'a');
}
vector<char> smallestChar(26);
for (int i = 0; i < 26; ++i)
smallestChar[i] = i + 'a';
for (int i = 0; i < 26; ++i) {
int root = uf.find(i);
smallestChar[root] = min(smallestChar[root], (char)(i + 'a'));
}
string result;
result.reserve(baseStr.size());
for (char c : baseStr) {
char rootChar = smallestChar[uf.find(c - 'a')];
result.push_back(rootChar);
}
return result;
}
int main() {
string s1 = "parker";
string s2 = "morris";
string baseStr = "parser";
cout << smallestEquivalentString(s1, s2, baseStr) << endl; // Output: "makkek"
return 0;
}class UnionFind {
constructor(size) {
this.parent = Array.from({ length: size }, (_, index) => index);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
this.parent[Math.max(rootX, rootY)] = Math.min(rootX, rootY);
}
}
}
function smallestEquivalentString(s1, s2, baseStr) {
const uf = new UnionFind(26);
for (let i = 0; i < s1.length; i++) {
uf.union(s1.charCodeAt(i) - 'a'.charCodeAt(0), s2.charCodeAt(i) - 'a'.charCodeAt(0));
}
const smallestChar = Array.from({ length: 26 }, (_, i) => String.fromCharCode(uf.find(i) + 'a'.charCodeAt(0)));
return Array.from(baseStr, c => smallestChar[c.charCodeAt(0) - 'a'.charCodeAt(0)]).join('');
}
// Example usage
console.log(smallestEquivalentString("parker", "morris", "parser")); // Output: "makkek"#include <stdio.h>
#include <string.h>
#define ALPHABET_SIZE 26
int find(int parent[], int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
void union_sets(int parent[], int rank[], int a, int b) {
int rootA = find(parent, a);
int rootB = find(parent, b);
if (rootA != rootB) {
if (rank[rootA] < rank[rootB])
parent[rootA] = rootB;
else if (rank[rootA] > rank[rootB])
parent[rootB] = rootA;
else {
parent[rootB] = rootA;
rank[rootA]++;
}
}
}
void smallestEquivalentString(const char* s1, const char* s2, const char* baseStr, char* result) {
int parent[ALPHABET_SIZE];
int rank[ALPHABET_SIZE] = {0};
for (int i = 0; i < ALPHABET_SIZE; i++) {
parent[i] = i;
}
int len = strlen(s1);
for (int i = 0; i < len; i++) {
union_sets(parent, rank, s1[i] - 'a', s2[i] - 'a');
}
for (int i = 0; i < ALPHABET_SIZE; i++) {
parent[i] = find(parent, i);
}
int baseLen = strlen(baseStr);
for (int i = 0; i < baseLen; i++) {
result[i] = parent[baseStr[i] - 'a'] + 'a';
}
result[baseLen] = '\0';
}
int main() {
const char *s1 = "parker";
const char *s2 = "morris";
const char *baseStr = "parser";
char result[100];
smallestEquivalentString(s1, s2, baseStr, result);
printf("%s\n", result); // Output: "makkek"
return 0;
}using System;
class Solution {
public string SmallestEquivalentString(string s1, string s2, string baseStr) {
int[] parent = new int[26];
for (int i = 0; i < 26; i++)
parent[i] = i;
for (int i = 0; i < s1.Length; i++) {
Union(parent, s1[i] - 'a', s2[i] - 'a');
}
for (int i = 0; i < 26; i++)
parent[i] = Find(parent, i);
char[] result = new char[baseStr.Length];
for (int i = 0; i < baseStr.Length; i++) {
result[i] = (char)(parent[baseStr[i] - 'a'] + 'a');
}
return new string(result);
}
private int Find(int[] parent, int x) {
if (parent[x] != x)
parent[x] = Find(parent, parent[x]);
return parent[x];
}
private void Union(int[] parent, int x, int y) {
int rootX = Find(parent, x);
int rootY = Find(parent, y);
if (rootX != rootY)
parent[Math.Max(rootX, rootY)] = Math.Min(rootX, rootY);
}
static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.SmallestEquivalentString("parker", "morris", "parser")); // Output: "makkek"
}
}This Python solution includes a UnionFind class to manage groupings of equivalent characters. By processing pairs of characters from s1 and s2 with the union operation, the equivalent sets are found. Finally, each character in baseStr is transformed to its smallest equivalent using these groupings.
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the length of baseStr.
Space Complexity: O(1), constant space usage for 26 characters.
Approach 2: DFS Graph Approach
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.
def build_graph(s1, s2):
graph = {chr(i): set() for i in range(ord('a'), ord('z') + 1)}
for a, b in zip(s1, s2):
graph[a].add(b)
graph[b].add(a)
return graph
def dfs(graph, node, visited, component):
stack = [node]
while stack:
current = stack.pop()
if current not in visited:
visited.add(current)
component.add(current)
stack.extend(graph[current] - visited)
return component
def smallest_equivalent_string(s1, s2, base_str):
graph = build_graph(s1, s2)
visited = set()
char_mapping = {}
for node in graph:
if node not in visited:
component = dfs(graph, node, visited, set())
min_char = min(component)
for char in component:
char_mapping[char] = min_char
return ''.join(char_mapping.get(c, c) for c in base_str)
# Example usage
s1 = "parker"
s2 = "morris"
base_str = "parser"
print(smallest_equivalent_string(s1, s2, base_str)) # Output: "makkek"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.
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.
Approach 3: Union Find
We can use Union Find (Disjoint Set Union, DSU) to handle the equivalence relations between characters. Each character can be regarded as a node, and the equivalence relations can be seen as edges connecting these nodes. With Union Find, we can group all equivalent characters together and quickly find the representative element for each character during queries. When performing union operations, we always set the representative element to be the lexicographically smallest character. This ensures that the final string is the lexicographically smallest equivalent string.
The time complexity is O((n + m) times log |\Sigma|) and the space complexity is O(|\Sigma|), where n is the length of strings s1 and s2, m is the length of baseStr, and |\Sigma| is the size of the character set, which is 26 in this problem.
function smallestEquivalentString(s1: string, s2: string, baseStr: string): string {
const p: number[] = Array.from({ length: 26 }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
for (let i = 0; i < s1.length; i++) {
const x = s1.charCodeAt(i) - 'a'.charCodeAt(0);
const y = s2.charCodeAt(i) - 'a'.charCodeAt(0);
const px = find(x);
const py = find(y);
if (px < py) {
p[py] = px;
} else {
p[px] = py;
}
}
const s: string[] = [];
for (let i = 0; i < baseStr.length; i++) {
const c = baseStr.charCodeAt(i) - 'a'.charCodeAt(0);
s.push(String.fromCharCode('a'.charCodeAt(0) + find(c)));
}
return s.join('');
}func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
p := make([]int, 26)
for i := 0; i < 26; i++ {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for i := 0; i < len(s1); i++ {
x := int(s1[i] - 'a')
y := int(s2[i] - 'a')
px := find(x)
py := find(y)
if px < py {
p[py] = px
} else {
p[px] = py
}
}
var s []byte
for i := 0; i < len(baseStr); i++ {
s = append(s, byte('a'+find(int(baseStr[i]-'a'))))
}
return string(s)
}impl Solution {
pub fn smallest_equivalent_string(s1: String, s2: String, base_str: String) -> String {
fn find(x: usize, p: &mut Vec<usize>) -> usize {
if p[x] != x {
p[x] = find(p[x], p);
}
p[x]
}
let mut p = (0..26).collect::<Vec<_>>();
for (a, b) in s1.bytes().zip(s2.bytes()) {
let x = (a - b'a') as usize;
let y = (b - b'a') as usize;
let px = find(x, &mut p);
let py = find(y, &mut p);
if px < py {
p[py] = px;
} else {
p[px] = py;
}
}
base_str
.bytes()
.map(|c| (b'a' + find((c - b'a') as usize, &mut p) as u8) as char)
.collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find Approach | Time Complexity: O(N + M), where N is the length of Space Complexity: O(1), constant space usage for 26 characters. |
| DFS Graph Approach | Time Complexity: O(N + M), where N is the length of Space Complexity: O(ALPHABET_SIZE), due to the storage of graph nodes and mappings. |
| Union Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O((n + m) * α(26)) | O(26) | Best general solution for equivalence relations; clean and optimal for grouping characters. |
| DFS Graph Traversal | O(26 + m + n) | O(26 + m) | Useful when modeling the problem explicitly as a graph and exploring connected components. |
Frequently asked questions
Is Lexicographically Smallest Equivalent String easy or hard?
The problem is rated Medium because it requires recognizing equivalence relationships and choosing the correct data structure. Once modeled with Union-Find or graph connected components, the implementation becomes straightforward.
Lexicographically Smallest Equivalent String Python/Java solution
Python and Java implementations typically use a Union-Find array of size 26 to represent lowercase characters. Each union operation merges two character sets while keeping the smallest root. After preprocessing, iterate through baseStr and map each character to its representative to build the final string.
How to solve Lexicographically Smallest Equivalent String in O(n)?
Build equivalence groups using Union-Find for the 26 lowercase characters. For every pair in s1 and s2, union their sets while keeping the lexicographically smaller root. Then iterate through baseStr and replace each character with the root of its set. Since the alphabet size is constant, the overall complexity behaves like O(n).
What is the best approach for Lexicographically Smallest Equivalent String?
Union-Find (Disjoint Set Union) is the most efficient and clean approach. Each character is treated as a node, and equivalent pairs are merged into the same set while keeping the smallest lexicographical character as the root. After building the sets, every character in baseStr is replaced with its set representative.
Is Lexicographically Smallest Equivalent String asked at Google/Amazon/Meta?
This problem is a common interview-style question related to Union-Find and graph connectivity. Variants of character equivalence and grouping problems have appeared in interviews at companies like Google, Amazon, and Meta, especially when testing knowledge of disjoint-set data structures.
What data structure is used in Lexicographically Smallest Equivalent String?
The primary data structure is Union-Find (Disjoint Set Union). It efficiently groups characters that are equivalent and quickly finds their smallest representative using path compression. A graph with DFS traversal can also be used to identify connected components.
What is the time complexity of Lexicographically Smallest Equivalent String?
The optimal Union-Find solution runs in O((n + m) * α(26)), where n is the length of baseStr and m is the length of s1/s2. Because the alphabet is limited to 26 lowercase letters, α(26) (inverse Ackermann function) is effectively constant, making the solution close to linear time.