Domain 2MediumMEDIUM

Lexicographically Smallest Equivalent String

Uses Disjoint Set Union (DSU) to group equivalent characters, ensuring the lexicographically smallest character is always maintained as the root of each component.

Domain: medium•Updated: 2026-09-08
#Union-Find#Array#O(N)#O(1)

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

  1. 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).
  2. 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.
  3. 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

  1. Initialize DSU: Create a parent array where each character points to itself initially (parent[i] = i). The indices correspond to characters ‘a’ through ‘z’.
  2. Process Equivalences: Iterate through A and B. 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.
  3. Transform S: Iterate through each character in string S. Find its root using the DSU structure and append the corresponding smallest equivalent character to the result list.
  4. Return Result: Join the characters into a final string.

Complexity Analysis

  • Time Complexity: O(N+M⋅α(26))O(N + M \cdot \alpha(26)), where NN is length of S and MM is length of A. Since α(k)\alpha(k) (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 NN or MM.

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 parent array 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 inside union ensures that even if we merge {a,b} then later {b,c}, the root will eventually be min(a, b, c).
  • Single Character Strings: Loop ranges handle length 1 correctly.