#1061

Medium

LeetCode Problem Workspace

Lexicographically Smallest Equivalent String

Determine the lexicographically smallest string by modeling character equivalences with union find efficiently.

Problem Statement

You are given two strings s1 and s2 of the same length and another string baseStr. Each position i indicates that s1[i] and s2[i] are equivalent characters, meaning they can be interchanged without affecting equivalence relations.

Characters are equivalent transitively: if 'a' is equivalent to 'b' and 'b' is equivalent to 'c', then 'a', 'b', and 'c' are all equivalent. Your task is to return a new string formed by replacing each character in baseStr with the lexicographically smallest equivalent character possible according to s1 and s2.

Examples

Example 1

Input: s1 = "parker", s2 = "morris", baseStr = "parser"

Output: "makkek"

Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is "makkek".

Example 2

Input: s1 = "hello", s2 = "world", baseStr = "hold"

Output: "hdld"

Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".

Example 3

Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"

Output: "aauaaaaada"

We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".

Constraints

1 <= s1.length, s2.length, baseStr <= 1000
s1.length == s2.length
s1, s2, and baseStr consist of lowercase English letters.

Solution Approach

Model equivalences using Union Find

Treat each character as a node in a union find structure. For each pair s1[i] and s2[i], union them, always ensuring the smallest lexicographical character becomes the representative. This step groups equivalent characters efficiently.

Transform the base string

Iterate through each character in baseStr. Replace it with the representative of its group in the union find structure, ensuring the smallest lexicographical character is used to minimize the final string.

Return the reconstructed string

After transforming all characters, join them to form the output string. Verify correctness against the equivalence graph to ensure all replacements respect the transitive equivalence relations established by s1 and s2.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N + M*α(N)) where N is the length of baseStr and M is the length of s1/s2 due to union find operations with path compression. Space complexity is O(26) for storing parent pointers for each lowercase character.

What Interviewers Usually Probe

Candidate recognizes transitive equivalence and applies union find correctly.
Candidate ensures lexicographical order is maintained in equivalence groups.
Candidate efficiently transforms baseStr without redundant lookups.

Common Pitfalls or Variants

Common pitfalls

Failing to merge equivalence groups correctly and violating transitive relations.
Replacing characters without considering the smallest lexicographical representative.
Overcomplicating union find by not taking advantage of the small fixed alphabet.

Follow-up variants

Apply the same approach to uppercase letters or extended Unicode characters.
Find the largest lexicographical equivalent string instead of the smallest.
Compute equivalence only for a subset of characters in baseStr.

FAQ

What pattern does this problem exemplify?

It uses the String plus Union Find pattern, modeling equivalences as a graph to quickly find minimal representatives.

Why do we need union find for Lexicographically Smallest Equivalent String?

Union find efficiently groups equivalent characters and tracks the smallest lexicographical representative for each group.

Can baseStr contain characters not in s1 or s2?

Yes, characters not present in s1 or s2 remain unchanged in the output string.

What is the main failure mode in this problem?

Failing to maintain transitive equivalences or ignoring the lexicographical order when merging groups.

How do we handle characters that map transitively through multiple pairs?

Union find merges each equivalence pair, propagating the smallest character as the group representative to handle all transitive relations.

terminal

Solution

Solution 1: Union Find

We can use Union Find (Disjoint Set Union, DSU) to handle the equivalence relations between characters. Each character can be regarded as a node, and the equivalence relations can be seen as edges connecting these nodes. With Union Find, we can group all equivalent characters together and quickly find the representative element for each character during queries. When performing union operations, we always set the representative element to be the lexicographically smallest character. This ensures that the final string is the lexicographically smallest equivalent string.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Continue Practicing

#990 satisfiability of equality equations #1202 smallest string with swaps #839 similar string groups