How do you solve Lexicographically Smallest Equivalent String on LeetCode?

Lexicographically Smallest Equivalent String (LeetCode #1061) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * α(n)) time complexity and O(n) space complexity. Key insight: Understanding equivalence relations helps in grouping characters effectively.

What is the brute force solution for Lexicographically Smallest Equivalent String?

The brute force approach for Lexicographically Smallest Equivalent String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every character in the base string and replacing it with its equivalent characters based on the equivalency information provided. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n * α(n)).

What algorithm or data structure is used to solve Lexicographically Smallest Equivalent String?

Lexicographically Smallest Equivalent String uses the following concepts: String, Union-Find. The recommended patterns to study are: Union-Find, Graph Theory.

What are the interview tips for Lexicographically Smallest Equivalent String?

Clearly explain your thought process when discussing equivalence relations. Practice implementing Union-Find, as it is a common pattern in many problems. Always consider edge cases, such as characters with no equivalents.

What are common mistakes when solving Lexicographically Smallest Equivalent String?

Failing to account for all equivalent characters when forming groups. Not using the Union-Find structure efficiently, leading to incorrect results.

#1061

Lexicographically Smallest Equivalent String

Medium

StringUnion-FindUnion-FindGraph Theory

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n * α(n))
Space	O(1)	O(n)

💡

Intuition

Time O(n * α(n))Space O(n)

The optimal solution uses Union-Find (Disjoint Set Union) to group equivalent characters efficiently. This allows us to find the smallest character in each group and replace characters in the base string accordingly.

⚙️

Algorithm

3 steps

1Step 1: Initialize a Union-Find structure to manage character groups.
2Step 2: For each pair of characters in s1 and s2, union them in the Union-Find structure.
3Step 3: For each character in baseStr, find its root representative in the Union-Find structure and replace it with the smallest character from its group.

solution.py36 lines

1# Full working Python code
2class UnionFind:
3    def __init__(self):
4        self.parent = {}
5
6    def find(self, x):
7        if x not in self.parent:
8            self.parent[x] = x
9        if self.parent[x] != x:
10            self.parent[x] = self.find(self.parent[x])
11        return self.parent[x]
12
13    def union(self, x, y):
14        rootX = self.find(x)
15        rootY = self.find(y)
16        if rootX != rootY:
17            self.parent[rootY] = rootX
18
19
20def smallestEquivalentString(s1, s2, baseStr):
21    uf = UnionFind()
22    for a, b in zip(s1, s2):
23        uf.union(a, b)
24    groups = {}
25    for char in uf.parent:
26        root = uf.find(char)
27        if root not in groups:
28            groups[root] = []
29        groups[root].append(char)
30    for group in groups.values():
31        group.sort()
32    result = []
33    for char in baseStr:
34        root = uf.find(char)
35        result.append(min(groups[uf.find(root)]))
36    return ''.join(result)

ℹ

Complexity note: The time complexity is O(n * α(n)), where α(n) is the inverse Ackermann function, which is very slow-growing, making this approach nearly linear in practice. The space complexity is O(n) due to the storage of the parent mapping.

1Understanding equivalence relations helps in grouping characters effectively.
2Union-Find is a powerful data structure for managing connected components.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.