1061: Lexicographically-Smallest-Equivalent-String
Medium

table of contents

This question immediately screams disjoint set union.

It basically just requires you to create a separate data structure called a disjoint set (this will be my attempt at explaining the disjoint set class).

In the optimised DisjointSet class, there contain 2 arrays:

In this class, there also contain 2 main methods:

The job of this function is to find the parent value of the disjoint set.

In it, however, contains the first optimisation: path compression, where find basically shrinks the “path” to the parent using recursion, meaning future find functions will be near constant time.

int find(int x) {
    return (x == parents[x]) ? x : (parents[x] = find(parents[x]));
}

The job of this function is to merge two disjoint sets

First, we have to check if they are disjoint in the first case. Take x and y as an example:

int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) return false;

If xRoot and yRoot are both equal, then we know they are already part of the same set and do not have to merge anything.

Else, we have merging to do.

Now, the second optimisation comes in: union by size

To ensure, that the “trees” we are creating are more balanced, it makes more sense to add the less dense “tree” to the more dense “tree” as that will minimise the amount of path compression we will have to do.

// swap "xRoot" and "yRoot" if:
if (size[xRoot] < size[yRoot]) {
    swap(xRoot, yRoot);
}
// add to the LARGER root
sizes[xRoot] += sizes[yRoot];
// update the root of the SMALLER root
parents[yRoot] = xRoot;
return true;

code

class DisjointSet {
private:
    vector<int> parents;
    vector<int> sizes;
public:
    DisjointSet (int size) : parents(size), sizes(size, 1) {
        iota(parents.begin(), parents.end(), 0);
    }

    int find(int x) {
        return (x == parents[x]) ? x : (parents[x] = find(parents[x]));
    }

    bool merge(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) return false;

        if (xRoot > yRoot) {
            swap(xRoot, yRoot);
        }
        sizes[xRoot] += sizes[yRoot];
        parents[yRoot] = xRoot;
        return true;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        DisjointSet dsu(26);

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

        string ans = "";
        for (char c : baseStr) {
            ans += char(dsu.find(c-'a'))+'a';
        }
        return ans;
    }
};

complexity

learnings