Problem of The Day: Lexicographically Smallest Equivalent String

Problem Statement

leetcode problem link

Union Find Approach [Accepted]

class UnionFind:
    def __init__(self):
        self.root = [i for i in range(26)]

    def find(self, x):
        if self.root[x] == x:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return

        # Always attach the lexicographically larger root to the smaller one
        if root_x < root_y:
            self.root[root_y] = root_x
        else:
            self.root[root_x] = root_y

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        uf = UnionFind()

        # Union all character pairs
        for c1, c2 in zip(s1, s2):
            i = ord(c1) - ord('a')
            j = ord(c2) - ord('a')
            uf.union(i, j)

        # Build result based on root representative
        res = []
        for c in baseStr:
            val = uf.find(ord(c) - ord('a'))
            res.append(chr(val + ord('a')))

        return "".join(res)

Editorial

Approach 1: Depth-First Search (DFS)

class Solution {
public:
    void DFS(int src, array<array<int, 26>, 26>& adjMatrix, array<int, 26>& visited, vector<int>& component, int& minChar) {
        // Mark the character as visited.
        visited[src] = 1;
        // Add it to the list.
        component.push_back(src);
        // Update the minimum character in the component.
        minChar = min(minChar, src);

        for (int i = 0; i < 26; i++) {
            // Perform DFS, if the edge exists and the node isn't visited yet.
            if (adjMatrix[src][i] && !visited[i]) {
                DFS(i, adjMatrix, visited, component, minChar);
            }
        }
    }

    string smallestEquivalentString(string s1, string s2, string baseStr) {
        // Adjacency matrix to store edges.
        array<array<int, 26>, 26> adjMatrix = {0};
        for (int i = 0; i < s1.size(); i++) {
            adjMatrix[s1[i] - 'a'][s2[i] - 'a'] = 1;
            adjMatrix[s2[i] - 'a'][s1[i] - 'a'] = 1;
        }

        // Array to store the final character mappings.
        array<int, 26> mappingChar = {0};
        for (int i = 0; i < 26; i++) {
            mappingChar[i] = i;
        }

        // Array to keep visited nodes during DFS.
        array<int, 26> visited = {0};
        for (int c = 0; c < 26; c++) {
            if (!visited[c]) {
                // Store the characters in the current component.
                vector<int> component;
                // Variable to store the minimum character in the component.
                int minChar = 27;

                DFS(c, adjMatrix, visited, component, minChar);

                // Map the characters in the component to the minimum character.
                for (int vertex : component) {
                    mappingChar[vertex] = minChar;
                }
            }
        }

        string ans;
        // Create the answer string.
        for (char c : baseStr) {
            ans += (char)(mappingChar[c - 'a'] + 'a');
        }

        return ans;
    }
};

Approach 2: Disjoint Set Union (DSU/Union Find)

class Solution {
public:
    array<int, 26> representative;

    // Returns the root representative of the component.
    int find(int x) {
        if (representative[x] == x) {
            return x;
        }

        return representative[x] = find(representative[x]);
    }

    // Perform union if x and y aren't in the same component.
    void performUnion(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return;
        }

        // Make the smaller character representative.
        if (x < y) {
            representative[y] = x;
        } else {
            representative[x] = y;
        }
    }

    string smallestEquivalentString(string s1, string s2, string baseStr) {
        // Make each character representative of itself.
        for (int i = 0; i < 26; i++) {
            representative[i] = i;
        }

        // Perform union merge for all the edges.
        for (int i = 0; i < s1.size(); i++) {
            performUnion(s1[i] - 'a', s2[i] - 'a');
        }

        string ans;
        // Create the answer string with final mappings.
        for (char c : baseStr) {
            ans += (char)(find(c - 'a') + 'a');
        }

        return ans;
    }
};