Problem 1061

Abstract / Summary

Given a string and equivalency mappings, find the smallest possible string by replacing each character with its mapped group using the earliest letter from each group.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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 ])
28 lines | 798 bytes | submitted October 5, 2023 | GitHub   19% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 81% (200k+ submissions).

Typical patterns to solve this problem:
  • String
  • Union Find
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 8.08 | σ = 0.83

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
30 links | 16 authors | 8 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

8 medium 1 hard
10 solutions   October 5, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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