Lexicographically Smallest Equivalent String — Medium Problem & Solution

Problem statement

Two strings s1 and s2 of equal length declare letter equivalences: for every index i, s1[i] and s2[i] are equivalent.

These equivalences behave as you would expect: every letter is equivalent to itself, equivalence is symmetric, and it is transitive (if a ~ b and b ~ c, then a ~ c).

Using them, you may replace any letter of baseStr with any letter equivalent to it. Return the lexicographically smallest string you can obtain.

Example 1

Input: s1 = "kairo", s2 = "codek", baseStr = "rock"
Output: eaaa
Explanation: The classes are {a, c, k, o}, {d, i} and {e, r}; each letter becomes the smallest of its class.

Example 2

Input: s1 = "abc", s2 = "bcd", baseStr = "dxb"
Output: axa
Explanation: `x` is only equivalent to itself.

Constraints

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

How to solve Lexicographically Smallest Equivalent String

Union-find on the alphabet: merge s1[i] with s2[i] for every index, keep the smallest letter as each set's root, then map each character of baseStr to its root.

Approach

1. Initialise root[c] = c for the 26 letters.
2. For each index i, find the roots of s1[i] and s2[i] and attach the larger root under the smaller one.
3. Build the answer by replacing every character of baseStr with find(character).

Why it works

The equivalence classes are exactly the connected components of the graph whose edges are the pairs (s1[i], s2[i]), which union-find computes. Characters of baseStr can be changed independently, so the lexicographically smallest result picks the minimum letter of each character's class at every position — and attaching the larger root under the smaller keeps that minimum at the root.

Complexity

• Time — O((n + m) · α(26))
• Space — O(26)

Pitfalls

• Union by smaller root, not by smaller letter of the pair — the pair's letters may not be their sets' roots.
• Letters that never appear in s1/s2 stay as they are.
• Equivalence is transitive: a ~ b and b ~ c means c can become a even though they never appear together.

Reference solution

Python

def smallestEquivalentString(s1: str, s2: str, baseStr: str) -> str:
    root = list(range(26))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for c1, c2 in zip(s1, s2):
        r1, r2 = find(ord(c1) - 97), find(ord(c2) - 97)
        if r1 < r2:
            root[r2] = r1
        elif r2 < r1:
            root[r1] = r2
    return "".join(chr(find(ord(c) - 97) + 97) for c in baseStr)

JavaScript

var smallestEquivalentString = function(s1, s2, baseStr) {
    var root = [];
    for (var i = 0; i < 26; i++) root.push(i);
    var find = function(x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    for (var k = 0; k < s1.length; k++) {
        var r1 = find(s1.charCodeAt(k) - 97), r2 = find(s2.charCodeAt(k) - 97);
        if (r1 < r2) root[r2] = r1;
        else if (r2 < r1) root[r1] = r2;
    }
    var out = [];
    for (var j = 0; j < baseStr.length; j++) out.push(String.fromCharCode(find(baseStr.charCodeAt(j) - 97) + 97));
    return out.join("");
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Ambiguous Coordinates Medium
• Generate Binary Strings Without Adjacent Zeros Medium
• Splitting a String Into Descending Consecutive Values Medium
• Letter Case Permutation Medium
• Extra Characters in a String Medium
• Minimum Cost to Make All Characters Equal Medium