MediumNo. 1061
Lexicographically Smallest Equivalent String — LeetCode 1061 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, String
- 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
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
- Time
- O((n + m) × log |Σ|)
- Space · auxiliary
- O(|Σ|), where n is the length of strings s1 and s2, m is the length of baseStr, and |Σ| is the size of the character set, which is 26 in this problem
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2157 | Groups of Strings | Hard |
| 0803 | Bricks Falling When Hit | Hard |
| 1627 | Graph Connectivity With Threshold | Hard |
| 1697 | Checking Existence of Edge Length Limited Paths | Hard |
| 1998 | GCD Sort of an Array | Hard |
| 2382 | Maximum Segment Sum After Removals | Hard |
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) × log |Σ|).
- What is the space complexity of LeetCode 1061. Lexicographically Smallest Equivalent String?
The Python solution on this page uses O(|Σ|), 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.