Problem statement

https://binarysearch.com/problems/String-Equivalence-Relations/

Solution

Equal to Leetcode 1061 Lexicographically Smallest Equivalent String.

Complexity

Time complexity is O(n + E), space complexity is O(n + E) as well.

Code

class Solution:
    def solve(self, A, B, S):
        G = defaultdict(list)
        for x, y in zip(A, B):
            if x == y: continue
            G[x] += [y]
            G[y] += [x]

        V, comps = set(), defaultdict(list)
        
        def dfs(node, i):
            V.add(node)
            comps[i].append(node)
            for neib in G[node]:
                if neib not in V:
                    dfs(neib, i)

        cnt, parents = 0, {}
        for node in G.keys():
            if node not in V:
                dfs(node, cnt)
                cnt += 1

        for i in comps.keys():
            mn = min(comps[i])
            for j in comps[i]:
                parents[j] = mn

        return "".join(parents.get(i, i) for i in S)