Python 1061.py
class Solution:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
parent = {}
for c in s1 + s2 + baseStr:
parent[c] = c
# union-find, copied from problem 721
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
if x < y:
parent[y] = x
else:
parent[x] = y
# mapping such that parent is minimized
for a, b in zip(s1, s2):
union(a, b)
# and resolve
return "".join([ find(c) for c in baseStr ])
Difficulty
and has an acceptance rate of about 81% (200k+ submissions).
Typical patterns to solve this problem:
- String
- Union Find
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation computes the lexicographically smallest equivalent string for a given baseStr using two source strings s1 and s2. It builds equivalence classes through a union-find (disjoint-set) structure, then maps each character of baseStr to the smallest character in its class. The algorithm proceeds in three logical phases: initialization of the disjoint-set, construction of equivalence relations, and final resolution of the output string.
Initialization of the Disjoint-Set
All characters that may appear in the computation are collected from the concatenation of s1, s2, and baseStr. Each character is initially its own parent, establishing a singleton set for every possible element.
parent = {}
for c in s1 + s2 + baseStr:
parent[c] = c
By iterating over the combined strings, the code guarantees that even characters appearing only in baseStr are present in the parent map, preventing lookup failures during later find operations.
Core Union-Find Operations
Two nested helper functions implement the classic union-find algorithm with path compression.
The find function recursively climbs the parent chain until it reaches the root of the set, compressing the path by assigning each visited node directly to the root. This reduces the depth of the tree for future queries.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
The union function merges two sets. After locating the roots of the two elements, it checks for equality to avoid redundant work. The merge direction is chosen based on the lexical order of the roots: the larger character points to the smaller one. This deterministic rule ensures that the root of each set is always the smallest character in that equivalence class.
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
if x < y:
parent[y] = x
else:
parent[x] = y
Building Equivalence Classes
The algorithm iterates over paired characters from s1 and s2, invoking union for each pair. This step creates the transitive closure of equivalence relations implied by the input strings.
for a, b in zip(s1, s2):
union(a, b)
Because union always attaches the larger character to the smaller one, the resulting structure automatically reflects the requirement that the smallest lexical representative be the root of each set.
Resolving the Result String
Finally, the code transforms baseStr by replacing each character with the root of its set, which is the minimal equivalent character. A list comprehension gathers the transformed characters, and join concatenates them into the final string.
return "".join([ find(c) for c in baseStr ])
The use of a list comprehension combined with join avoids repeated string concatenation, which would be costly in Python due to immutable string objects.
Edge Cases Handled
The implementation gracefully handles characters that appear exclusively in baseStr. Since those characters are added to the parent map during initialization, the subsequent find call returns the character itself, leaving it unchanged in the output.
Duplicate mappings, where the same pair of characters appears multiple times in s1 and s2, are safely ignored because union detects identical roots and returns early.
Self-mapping pairs (e.g., a paired with a) also result in a no-op, as the roots are equal and the early return prevents unnecessary modifications.
The lexical ordering rule in union ensures that even when multiple characters are transitively linked (e.g., a~c, c~b), the final root will be the smallest character among the group (a in this case), satisfying the problem’s requirement without additional post-processing.
Performance Optimizations
Path compression in find dramatically flattens the tree structure, turning subsequent find operations into near-constant time lookups.
Choosing the smaller lexical character as the parent during union eliminates the need for a separate rank or size heuristic while still providing a deterministic and shallow hierarchy.
Initializing the parent dictionary in a single pass over the concatenated input strings avoids repeated existence checks or conditional insertions later on.
The final string construction leverages a list comprehension and a single join, which is more efficient than concatenating characters one by one inside a loop.
Collectively, these choices keep the overall runtime linear with respect to the total length of the input strings, and the memory footprint is bounded by the number of distinct characters involved.
ELI5 - Simplified Explanation
Think of this like a game where you have lots of building blocks with different letters on them. Some of these blocks are connected to each other because they are actually the same thing.
First, the code gives every single letter its own box. At the very beginning, every letter is just thinking that it is itself.
Next, there is a special rule for when we see two letters paired together. It looks at the two letters and decides which one is the smallest, kind of like how we decide which number comes first when we count. The computer then picks that smallest letter to be the leader for the other one. By doing this over and over, every letter eventually finds a group leader.
The last part of the game happens when we look at a secret message. For every letter in that message, the computer checks to see who the leader of that letter is. Since the leader is always the smallest possible version of that group, the computer swaps out every original letter for its little leader. It puts all those new letters together to make a brand new message.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | Java | C++ | Python | TS | ||||
| WalkCCC | Java | C++ | |||||||
| leetcode.ca | Java | C# | C++ | Python | Go | Rust | TS | ||
| LeetcodeHelp | Java | C++ | Python | ||||||
| Progiez | Java | C++ | Python | ||||||
| github | BigEggStudy | C# | |||||||
| black-shadows | C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| JoshCrozier | JS | ||||||||
| shreymehul | C# | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| varunu28 | Java | ||||||||
| vthwang | Java | ||||||||
| wisdompeak | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Java | ||||||||
| leetcode.ca | C++, C#, Go, Java, Python, Rust, TypeScript | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| BigEggStudy | C# | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| JoshCrozier | JavaScript | ||||||||
| shreymehul | C# | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| varunu28 | Java | ||||||||
| vthwang | Java | ||||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 417: Pacific Atlantic Water Flow
- problem 442: Find All Duplicates in an Array
- problem 457: Circular Array Loop
- problem 554: Brick Wall
- problem 565: Array Nesting
- problem 647: Palindromic Substrings
- problem 721: Accounts Merge
- problem 785: Is Graph Bipartite?
- problem 273: Integer to English Words
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality