Lexicographically Smallest Equivalent String

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:

• one called parents, containing the parent values of the disjoint set each value is in
• one called sizes, containing the size (or number of elements) present in that respective set
  • you could also do by ranks (or the height) of the tree representing the set (but they are basically identical)
  • have extremely, extremely, extremely minor performance differences as size tends to have more balanced trees
    • as a tree can be of higher rank, but contain less nodes

In this class, there also contain 2 main methods:

• find

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]));
}

• merge/union

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

• Time: O(N * α(n)) where α(n) is the inverse Ackermann function and is basically constant
• Space: O(1)

learnings

• there is a great simple guide on USACO on disjoint set union
  • it actually does not go into the logic very much
  • this does a better job at explaining the logic