Problem Breakdown
We are given two strings A and B defining equivalence pairs between characters at corresponding indices (i.e., A[i] == B[i]). These equivalences follow the properties of an equivalence relation, effectively partitioning lowercase English letters into disjoint connected components. We must transform a target string S such that every character is replaced by its equivalent from these groups to achieve the lexicographically smallest possible result. Characters in S not present in any defined group remain unchanged.
Intuition
- Graph Representation: The equivalence relation defines nodes (‘a’-‘z’) and edges connecting them based on pairs
(A[i], B[i]). Transitivity implies we need to find connected components (sets of equivalent characters). - DSU Structure: A Disjoint Set Union (Union-Find) data structure is ideal for managing these sets efficiently. It allows us to merge sets and query the representative element in nearly constant time.
- Lexicographical Requirement: Standard DSU finds any representative. To satisfy the “smallest equivalent” requirement, we must ensure that when merging two components, the new root is always the lexicographically smallest character index among them. This way,
find(char)directly returns the minimum valid replacement for any character in its group.
Approach
- Initialize DSU: Create a parent array where each character points to itself initially (
parent[i] = i). The indices correspond to characters ‘a’ through ‘z’. - Process Equivalences: Iterate through
AandB. For every pair(char_a, char_b):- Find the root of both characters using path compression.
- If they belong to different components (different roots), merge them by making the smaller index character the parent of the larger one. This ensures the component’s representative is always the minimum value.
- Transform
S: Iterate through each character in stringS. Find its root using the DSU structure and append the corresponding smallest equivalent character to the result list. - Return Result: Join the characters into a final string.
Complexity Analysis
- Time Complexity: , where is length of
Sand is length ofA. Since (inverse Ackermann function) for 26 characters is effectively constant, the complexity simplifies to O(N). - Space Complexity: O(1) auxiliary space. We use a fixed-size array of size 26 regardless of input string lengths or .
Solution
class Solution:
def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
# Initialize parent for each character 'a'-'z'.
# Index i corresponds to ord(char) - 97.
parent = list(range(26))
def find(i):
"""Find with path compression."""
if parent[i] != i:
parent[i] = find(parent[i])
return parent[i]
def union(i, j):
"""Union sets ensuring the smaller character becomes root."""
root_i = find(i)
root_j = find(j)
# If they are in different components, merge them.
if root_i != root_j:
# Always make the lexicographically smaller index (char) the parent/root
if root_i < root_j:
parent[root_j] = root_i
else:
parent[root_i] = root_j
# Process all equivalence pairs from A and B
for char_a, char_b in zip(A, B):
union(ord(char_a) - 97, ord(char_b) - 97)
# Build the result string by replacing each character with its smallest equivalent
res = []
for char_s in S:
root_idx = find(ord(char_s) - 97)
res.append(chr(root_idx + 97))
return "".join(res)
Edge Cases Handled
- Characters not present in A/B: The
parentarray initializes every character to itself. If a char from S never appears in the union operations, its root remains itself (original value), preserving it correctly. - Transitivity Chains: DSU handles chains naturally (
a==b,b==c->find(a)returns min of all). The specific logic insideunionensures that even if we merge{a,b}then later{b,c}, the root will eventually bemin(a, b, c). - Single Character Strings: Loop ranges handle length 1 correctly.