What is the time complexity of LeetCode 1061. Lexicographically Smallest Equivalent String?

The Python solution on this page runs in O((n + m) \times \log |\Sigma|).

What is the space complexity of LeetCode 1061. Lexicographically Smallest Equivalent String?

The Python solution on this page uses 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 auxiliary space.

Lexicographically Smallest Equivalent String — LeetCode 1061 Python Solution

MediumUnion FindString

Problem: #1061
Pattern: Union-Find
Reading time: 3 min
Source: leetcode.com

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.

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

Python solution

Python

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

Measure	Complexity
Time	O((n + m) \times \log \|\Sigma\|)
Space	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 auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1061. Lexicographically Smallest Equivalent String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1061. Lexicographically Smallest Equivalent String?: LeetCode 1061. Lexicographically Smallest Equivalent String is rated Medium on LeetCode.
What is the time complexity of LeetCode 1061. Lexicographically Smallest Equivalent String?: The Python solution on this page runs in O((n + m) \times \log |\Sigma|).
What is the space complexity of LeetCode 1061. Lexicographically Smallest Equivalent String?: The Python solution on this page uses 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 auxiliary space.
What topics does LeetCode 1061. Lexicographically Smallest Equivalent String cover?: LeetCode 1061. Lexicographically Smallest Equivalent String is tagged Union Find and String on LeetCode.