Code Implementation

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        parent = [i for i in range(26)]

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                # Always attach larger to smaller for lex order
                if px < py:
                    parent[py] = px
                else:
                    parent[px] = py

        for a, b in zip(s1, s2):
            union(ord(a) - ord('a'), ord(b) - ord('a'))

        res = []
        for c in baseStr:
            res.append(chr(find(ord(c) - ord('a')) + ord('a')))
        return ''.join(res)
      

class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        vector<int> parent(26);
        for (int i = 0; i < 26; ++i) parent[i] = i;

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };

        auto unite = [&](int x, int y) {
            int px = find(x), py = find(y);
            if (px != py) {
                if (px < py) parent[py] = px;
                else parent[px] = py;
            }
        };

        for (int i = 0; i < s1.size(); ++i)
            unite(s1[i] - 'a', s2[i] - 'a');

        string res;
        for (char c : baseStr)
            res += char(find(c - 'a') + 'a');
        return res;
    }
};
      

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) parent[i] = i;

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        for (int i = 0; i < s1.length(); i++) {
            int a = s1.charAt(i) - 'a', b = s2.charAt(i) - 'a';
            int pa = find(a), pb = find(b);
            if (pa != pb) {
                if (pa < pb) parent[pb] = pa;
                else parent[pa] = pb;
            }
        }

        StringBuilder res = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            res.append((char) (find(c - 'a') + 'a'));
        }
        return res.toString();
    }

    // Helper for find in Java (since local function not allowed)
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}
      

var smallestEquivalentString = function(s1, s2, baseStr) {
    let parent = Array(26).fill(0).map((_,i) => i);

    function find(x) {
        if (parent[x] !== x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    function union(x, y) {
        let px = find(x), py = find(y);
        if (px !== py) {
            if (px < py) parent[py] = px;
            else parent[px] = py;
        }
    }

    for (let i = 0; i < s1.length; i++)
        union(s1.charCodeAt(i)-97, s2.charCodeAt(i)-97);

    let res = '';
    for (let c of baseStr)
        res += String.fromCharCode(find(c.charCodeAt(0)-97)+97);
    return res;
};
      

Problem Description

You are given two strings, s1 and s2, of equal length, and a third string baseStr. Each character in s1 can be considered equivalent to the character in the same position in s2. This equivalence is transitive: if a is equivalent to b and b is equivalent to c, then a is equivalent to c.

Your goal is to transform baseStr into the lexicographically smallest string possible by replacing each character with any of its equivalents (including itself).

Constraints:

• Each letter can be replaced with any of its equivalents, directly or through transitive equivalence.
• There is always exactly one solution for the given inputs.
• You cannot use elements outside the equivalence relations defined by s1 and s2.

Thought Process

At first glance, you might think to directly replace each character in baseStr with the smallest equivalent character found in s1 and s2. However, because equivalence is transitive, equivalence classes can form larger groups (e.g., a ~ b ~ c means all three are equivalent). So, to ensure the smallest lexicographical result, we must always pick the smallest character in each equivalence group.

A brute-force approach would be to, for each character, recursively find all its equivalents and pick the smallest. But this is inefficient, especially for long strings or many equivalence relations. Instead, we can use the union-find (disjoint set) data structure, which efficiently manages grouping and finding the minimum representative for each group.

This approach shifts our thinking from direct replacement to grouping and mapping: we first build all equivalence groups, then for each character in baseStr, find its group's "smallest" representative.

Solution Approach

We use a union-find (disjoint set) structure to manage the equivalence classes of characters. Here’s how we proceed:

1. Initialize: Create a parent array for all 26 lowercase letters, where each letter starts as its own parent.
2. Union Operations: For each pair of characters at the same position in s1 and s2, union their groups. During union, always attach the group with the higher letter to the group with the lower letter to ensure the smallest letter becomes the representative.
3. Find Operation: For each character in baseStr, use the find operation to retrieve the smallest equivalent character in its group.
4. Build Result: Construct the output string by replacing each character in baseStr with its group’s smallest representative.

Why union-find? Union-find allows us to efficiently merge equivalence classes and always retrieve the smallest representative for any character in near-constant time.

Example Walkthrough

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

1. Build equivalence relations:
   • p ~ m
   • a ~ o
   • r ~ r
   • k ~ r
   • e ~ i
   • r ~ s
2. After applying union-find, the equivalence groups are:
   • Group 1: a, o
   • Group 2: e, i
   • Group 3: k, r, s
   • Group 4: m, p
   In each group, the smallest letter is the representative.
3. For each character in baseStr ("p a r s e r"):
   • p → m,p group → 'm'
   • a → a,o group → 'a'
   • r → k,r,s group → 'k'
   • s → k,r,s group → 'k'
   • e → e,i group → 'e'
   • r → k,r,s group → 'k'
   So, the result is "maksek".

Time and Space Complexity

• Brute-force approach: For each character in baseStr, recursively find all equivalents (potentially O(N^2) or worse for large equivalence chains).
• Optimized union-find approach:
  • Building unions: O(N), where N is the length of s1/s2.
  • Find operations: O(1) amortized per operation thanks to path compression.
  • Building the result: O(M), where M is the length of baseStr.
  • Total time complexity: O(N + M).
  • Space complexity: O(1), since the parent array is fixed size (26 for lowercase letters).

Summary

The key insight is recognizing that equivalence relations can be efficiently managed with union-find, allowing us to quickly determine the smallest representative for any group of equivalent characters. By always uniting groups in lexicographical order, we guarantee the smallest possible output. This approach is both elegant and efficient, taking advantage of the fixed alphabet size and the properties of disjoint set data structures.