Leetcode #1061: Lexicographically Smallest Equivalent String

In this guide, we solve Leetcode #1061 Lexicographically Smallest Equivalent String in Python and focus on the core idea that makes the solution efficient.

You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.

Leetcode

Problem Statement

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.

Quick Facts

Difficulty: Medium
Premium: No
Tags: Union Find, String

Intuition

We need to merge components and check connectivity efficiently.

Union-Find supports near-constant-time merges and finds.

Approach

Initialize each node as its own parent and union pairs as you scan.

Use path compression to keep operations fast.

Steps:

Initialize parent arrays.
Union related nodes.
Use find to check connectivity.

Example

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".

Python Solution

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(26))
        for a, b in zip(s1, s2):
            x, y = ord(a) - ord("a"), ord(b) - ord("a")
            px, py = find(x), find(y)
            if px < py:
                p[py] = px
            else:
                p[px] = py
        return "".join(chr(find(ord(c) - ord("a")) + ord("a")) for c in baseStr)

Complexity

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. 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.

Edge Cases and Pitfalls

Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.

Summary

This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.

Example

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".

Python Solution

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(26))
        for a, b in zip(s1, s2):
            x, y = ord(a) - ord("a"), ord(b) - ord("a")
            px, py = find(x), find(y)
            if px < py:
                p[py] = px
            else:
                p[px] = py
        return "".join(chr(find(ord(c) - ord("a")) + ord("a")) for c in baseStr)

Complexity

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. 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.

Leetcode #1061: Lexicographically Smallest Equivalent String

Problem Statement

Quick Facts

Intuition

Approach

Example

Python Solution

Complexity

Edge Cases and Pitfalls

Summary

Ace your next coding interview

Leetcode #1061: Lexicographically Smallest Equivalent String

Problem Statement

Quick Facts

Intuition

Approach

Example

Python Solution

Complexity

Edge Cases and Pitfalls

Summary

Ace your next coding interview