🔤 Beginner-Friendly Guide to Solving "Lexicographically Smallest Equivalent String" | LeetCode 1061 (C++ | JavaScript | Python)

#algorithms #beginners #programming #productivity

Hello, curious coders! 🧑‍💻 Today, we're diving into a fun string manipulation and graph problem from LeetCode — Lexicographically Smallest Equivalent String. We'll break it down step-by-step and walk through a clean and efficient solution using Disjoint Set Union (Union-Find). Let's get started! 🚀

📘 Problem Statement

You're given two strings s1 and s2 of the same length. Each index in these strings represents an equivalency relationship — for example, if s1[i] == 'a' and s2[i] == 'b', then 'a' and 'b' are equivalent. These equivalencies follow the rules of an equivalence relation:

Reflexive: 'a' == 'a'
Symmetric: If 'a' == 'b', then 'b' == 'a'
Transitive: If 'a' == 'b' and 'b' == 'c', then 'a' == 'c'

You're also given a third string, baseStr. Your task is to transform every character in baseStr to the lexicographically smallest equivalent character possible using the relationships defined in s1 and s2.

🧠 Intuition and Approach

We treat each letter as a node in a graph, and each pair (s1[i], s2[i]) as an edge connecting two nodes. The idea is to group all connected characters and replace each one in baseStr with the smallest character in its group.

This is where Disjoint Set Union (DSU) comes to the rescue! 💡

⚙️ Key DSU Operations

Find: Determine the root representative of a character.
Union: Connect two characters, always attaching the one with the lexicographically smaller character as the parent.

👨‍💻 C++ Implementation with `unionByLex()`

class Solution {
public:
    class DSU {
        vector<int> parent;
    public:
        DSU(int n) {
            parent.resize(n);
            for (int i = 0; i < n; ++i) parent[i] = i;
        }

        int findPar(int u) {
            if (parent[u] != u) parent[u] = findPar(parent[u]);
            return parent[u];
        }

        void unionByLex(int u, int v) {
            int pu = findPar(u);
            int pv = findPar(v);
            if (pu == pv) return;
            if (pu < pv) parent[pv] = pu;
            else parent[pu] = pv;
        }
    };

    string smallestEquivalentString(string s1, string s2, string baseStr) {
        DSU dsu(26);

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

        for (int i = 0; i < baseStr.size(); ++i) {
            baseStr[i] = dsu.findPar(baseStr[i] - 'a') + 'a';
        }

        return baseStr;
    }
};

🌐 JavaScript Version

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

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

    const union = (x, y) => {
        let px = find(x);
        let py = find(y);
        if (px === py) return;
        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 result = "";
    for (let ch of baseStr) {
        result += String.fromCharCode(find(ch.charCodeAt(0) - 97) + 97);
    }

    return result;
};

🐍 Python Version

def smallestEquivalentString(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 = find(x)
        py = find(y)
        if px == py:
            return
        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'))

    result = ''
    for ch in baseStr:
        result += chr(find(ord(ch) - ord('a')) + ord('a'))

    return result

🔁 Test Cases

Let's validate our solution with a few diverse cases:

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

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

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

// Unique test case:
Input:
    s1 = "abc", s2 = "xyz", baseStr = "cba"
Output: "xyz"   // Because 'a' -> 'x', 'b' -> 'y', 'c' -> 'z'

Input:
    s1 = "abcabc", s2 = "defdef", baseStr = "fed"
Output: "aaa"   // All letters map to the smallest in their equivalence class

📈 Time and Space Complexity

Time Complexity: O(n + m)  // n = s1.size(), m = baseStr.size()
Space Complexity: O(1)     // Only 26 lowercase letters stored

✨ Wrap Up

This problem is a perfect combo of strings and graphs and gives you a solid practice on Union-Find — a super important concept in computer science. Learning it here with such a fun problem is a win-win! 🎯

If you found this helpful, feel free to ❤️ and follow for more beginner-friendly walkthroughs!

Happy coding! 👨‍💻✨